[프로그래머스] 타겟 넘버

풀이 과정

1. queue를 통해 BFS를 구현한다.queue에 들어가는 요소는 (total,index)
   • index : 이번 while문에서 열어볼 numbers의 인덱스 번호
   • total : 이전까지 수들의 합

que = deque()
que.append((0,0)) # 토탈은 0, 0번 인덱스로 시작할 예정

2. 자주 사용할 numbers 배열의 길이를 미리 생성하고, 정답 answer에 0으로 시작한다.

length = len(numbers)
answer = 0

3. while문으로 BFS를 구현한다.
   • 만약 index가 length보다 작다면. 해당 인데스의 수를 더하거나 빼서 큐에 넣는다.
   • index가 length보다 작지 않고, total과 target이 같은 수라면 answer에 1을 추가한다.

while que:
    total,index = que.popleft()
    if index < length:
        que.append((total + numbers[index],index+1))
        que.append((total - numbers[index],index+1))
    elif total == target:
        answer += 1

4. return answer

코드 전문

def solution(numbers, target):
    from collections import deque
    que = deque()
    que.append((0,0)) # 토탈은 0, 0번 인덱스로 시작할 예정
    length = len(numbers)
    answer = 0
    while que:
        total,index = que.popleft()
        if index < length:
            que.append((total + numbers[index],index+1))
            que.append((total - numbers[index],index+1))
        elif total == target:
            answer += 1
    return answer
print(solution([1,1,1,1,1],3))
print(solution([4,1,2,1],4))