[Programmers] 타겟 넘버 (Python)

코딩테스트 연습 - 타겟 넘버

 

 

예전에 풀었던 BFS / DFS를 오랜만에 다시 풀어봤다!

주어진 숫자로 타겟 넘버를 만드는 방법이 몇가지 있는지 세보는 문제이다.

이때 주어진 숫자의 순서는 바꿀 수가 없다!

 

방법은 간단하다.

앞에서부터 순서대로 더하거나 빼는 케이스를 해보고, 타겟 넘버가 되는 케이스를 세어주면 된다.

 

1) BFS 풀이

def bfs(start) :
    answer = 0
    q = deque([])
    q.append((numbers[start], start))
    q.append((-numbers[start], start))
    while q :
        result, index = q.popleft()
        if index == len(numbers)-1 :
            if result == target :
                answer += 1
        else :
            index += 1
            q.append((result + numbers[index], index))
            q.append((result - numbers[index], index))
    return answer
    answer = bfs(0)

 

 

2) DFS 풀이

def dfs(result, idx) :
    answer = 0
    if idx == len(numbers)-1 :
        if result == target :
            answer += 1
    else :
        idx += 1
        answer += dfs(result+numbers[idx], idx)
        answer += dfs(result-numbers[idx], idx)
    return answer
    
    answer = dfs(0, -1)