[프로그래머스] 타겟 넘버 (BFS/DFS) 파이썬

다른 사람의 풀이

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque([(0, 0)]) # sum, level
    while queue:
        s, l = queue.popleft()
        if l > len(numbers):
            break
        elif l == len(numbers) and s == target:
            answer += 1
        queue.append((s+numbers[l-1], l+1))
        queue.append((s-numbers[l-1], l+1))

    return answer

 

sum, level이라는 2개의 tuple를 queue를 활용해서 만든풀이

 

queue에 들어가는 tuple를 append하는 코드를 보면,

s는 sum이라고 표현되어있지만

s는 number list에서 s의 index 왼쪽에 있는 element와 합한 결과로 갱신한다.

동시에 l이라는 level도 index가 추가된 연산이기 때문에 += 1

 

ex. list = [1,2,3,4,5]

deque([(5, 1), (-5, 1)])
deque([(-5, 1), (6, 2), (4, 2)])
deque([(6, 2), (4, 2), (-4, 2), (-6, 2)])
deque([(4, 2), (-4, 2), (-6, 2), (8, 3), (4, 3)])
deque([(-4, 2), (-6, 2), (8, 3), (4, 3), (6, 3), (2, 3)])
deque([(-6, 2), (8, 3), (4, 3), (6, 3), (2, 3), (-2, 3), (-6, 3)])
deque([(8, 3), (4, 3), (6, 3), (2, 3), (-2, 3), (-6, 3), (-4, 3), (-8, 3)])

 

이런식으로 queue에 tuple이 저장되게 된다.

idx를 증가시키면서 해당 idx의 element와의 +,-로 한 연산을 idx의 level?과 함께 tuple로 저장하는 것이다.

 

l이 numbers 리스트의 len를 초과하면 while문을 빠져나간다.

빠져나가기 전까지는 문제에서 요구한 조건에 맞을 경우 answer += 1을 해주는 것이다.