[Algorithm] 프로그래머스 '타겟넘버'(with python)

📝 문제

💡 아이디어

1. 주어진 숫자를 더하거나 빼기 - BFS ✅

2. 모든 숫자를 나열한 후 목표숫자가 되는지 확인 - DFS

풀이 1

def solution(numbers, target):
    nodes = [0]
    count = 0
    for num in numbers:
        temp = []
        for node in nodes:
            temp.append(node + num)
            temp.append(node - num)
        nodes = temp
    for node in nodes:
        if node == target:
            count += 1
    return count

풀이2

🚨 deque 활용하기

from collections import deque
def solution(numbers, target):
    queue = deque([(0, 0)])
    count = 0
    while queue:
        temp, idx = queue.popleft() 
        if idx == len(numbers):
            if temp == target:
                count += 1
        else:
            queue.append((temp + numbers[idx], idx+1))
            queue.append((temp - numbers[idx], idx+1))
    return count