[프로그래머스] BFS - 타겟 넘버 (Python)

👻 문제

• 문제 설명
  n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

  -1+1+1+1+1 = 3
  +1-1+1+1+1 = 3
  +1+1-1+1+1 = 3
  +1+1+1-1+1 = 3
  +1+1+1+1-1 = 3

  사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

• 제한사항
  주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
  각 숫자는 1 이상 50 이하인 자연수입니다.
  타겟 넘버는 1 이상 1000 이하인 자연수입니다.

• 입출력 예
  

• 입출력 예 설명

  +4+1-2+1 = 4
  +4-1+2-1 = 4
  총 2가지 방법이 있으므로, 2를 return 합니다.

👩‍💻 My cording

풀이 : deque, append, popleft(), while문, if문 사용

from collections import deque

def solution(numbers, target):
  cnt = 0
  queue = deque()
  n = len(numbers)

  # 첫번째 자리 수 세팅
  queue.append([numbers[0], 0])
  queue.append([numbers[0]*-1, 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: # 남은 연산들의 결과가 target과 같을 때, cnt+=1
      if temp == target:
        cnt+= 1

  return cnt

---

💡 이해를 위한 과정 예시
처음에 해당 코드를 봤을 때, 바로 연상되지 않았다.
아래 과정 예시를 써보면서 작성된 코드의 목적은 어느정도 이해가 되었지만,
여전히 해당 코딩을 작성하라고 하면 머리에 바로 그려지지 않는다. 🥲

def solution([1,1,1], 1)  

pop[1, 0], pop[-1, 0]
pop[1+1, 1], pop[1-1, 1]
pop[-1+1, 1], pop[-1-1, 1]

-- idx = n 성립 stop --

[1+1+1, 2], [1+1-1, 2], 
[1-1+1, 2], [1-1-1, 2],
[-1+1+1, 2], [-1+1-1, 2],
[-1-1+1, 2], [-1-1-1, 2]
→ 연산결과 = target인 것은 3개