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

문제

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

정답

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

풀이

1. 큐에 주어진 숫자들의 합과 인덱스를 저장함
2. 큐가 비어 있지 않은 한 반복문 수행
   a. 큐에서 가장 앞에 있는 원소(합,인덱스)를 꺼냄
   b. 인덱스를 1 증가시킴
   c. 인덱스가 숫자 리스트의 길이보다 작다면, 숫자 리스트의 다음 숫자와 그 수의 음수를 더한 값을 큐에 추가함
   d. 인덱스가 숫자 리스트의 길이와 같거나 크면(리스트의 모든 숫자를 사용한 경우), 합이 타겟 값과 같은지 확인하고, 같다면 정답의 개수를 증가시키고 큐에는 추가하지 않음

numbers = [1, 1, 1, 1, 1] target = 3 일때

1. 큐는 [(1, 0), (-1, 0)]로 초기화된다. (첫 번째 숫자와 그 음수를 넣음)
2. 큐에서 (1,0)을 꺼내고, 인덱스를 증가시킨 후 다음 숫자 1과 그 음수를 더한 값을 큐에 넣는다.
   큐는 [(-1, 0),(2, 1),(0, 1)]가 된다.
3. (2,1)을 꺼내고, 인덱스를 증가시킨 후, 다음 숫자 1과 그 음수를 더한 값을 큐에 넣는다. 큐는 [(0, 1), (-1, 0), (3, 2), (1, 2)]가 된다.
4. 모든 경우를 탐색하고, 타겟 값과 같은 합을 찾을 때마다 answer ++
5. answer 반환

index 값을 증가시키는 이유는 numbers 리스트의 다음 숫자로 넘어갈 때마다 가능한 모든 조합을 고려하기 위함임.
numbers = [1, 2, 3]이고 target = 6인 경우
1. idx = 0, number = 1
큐 : [1, 0], [-1, 0]
2. 큐에서 [1,0]을 꺼내고 idx =1, number =2
큐: [-1,0][1+2,1] [1,-2,1]
3. 큐에서 [-1,0]을 꺼내고 idx = 1, number = 2
큐: [3,1][-1,1] [-1+2,1][-1-2,1]