[프로그래머스 | 파이썬] 타겟 넘버

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43165

코드

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque()
    queue.append('+')
    queue.append('-')
    
    while queue:
        op = queue.popleft()
        
        if len(op) == len(numbers):
            
            total = 0
            for i in range(len(numbers)):
                if op[i] == '+':
                    total += numbers[i]
                if op[i] == '-':
                    total -= numbers[i]
            if total == target:
                answer += 1

            continue
            
        queue.append(op + '+')
        queue.append(op + '-')
    
    return answer

풀이 설명

깊이/너비 우선 탐색이라는 유형이 아니었다면 permutations 써서 풀었을 것 같다.
여기서는 문제 유형이 깊이/너비 우선 탐색으로 주어졌기 때문에 BFS로 풀었다!
queue에 "+", "-"를 각각 넣어서 초기화해 준 다음, queue를 하나씩 pop해가면서 "+" 또는 "-"를 추가해 다시 queue에 넣어주었다.
이때, pop된 연산자 세트가 numbers 배열의 길이와 일치할 경우에는 연산자 세트로 나올 수 있는 총합을 구했다.
총합이 target 과 일치하면 answer를 1 증가시키면 된다!