소수 찾기

설명

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

# 1 / 0,2 / -1,1,1,3 / ...
# 완전이진트리되는듯?
# 이런것도 BFS인가? 내가 생각하는 BFS 코테 문제랑은 다르더라
# 하나 pop하고 number 하나 꺼내서 다 더해서 노드 추가 반복

from collections import deque
def solution(numbers, target):
    answer = 0
    dq = deque()
    depth = 0
    dq.append((0,-1))
    n = len(numbers)
    while depth < n:
        number = numbers.pop()
        while dq[0][1] <= depth:
            node = dq.popleft()
            dq.append((node[0]+number, depth+1))
            dq.append((node[0]-number, depth+1))
        depth += 1
    
    for leaf in dq:
        if leaf[0] == target:
            answer += 1
            
    print(answer)
    return answer

• BFS라는게 그냥 그런 식으로 그래프를 탐색하면 BFS 문제인가보다.
• 이 문제의 경우 모든 케이스를 생각해보면 완전 이진트리가 나온다.
• 우선 모든 경우의 트리를 만든 뒤 leaf 노드에서 타겟 값을 찾는다.