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

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

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

BFS로 풀었다.

BFS는 기본적으로 큐를 쓰는데, 파이썬은 deque를 쓰면 편하다.

 

이 문제는 numbers를 하나하나 더하거나 빼면서 target과 같게 할 수 있는 경우의 수를 구하는 문제다.

 

내가 푼 방법은 다음과 같다.

 

1. 큐 아이템을 (현재 값, 현재까지 탐색한 위치) 로 한다.
2. 처음에 [-1,0], [1,0] ( 첫번째 값의 +,- 값) 을  큐에 넣는다.
3. 큐가 빌때까지:
   1. 탐색위치가 numbers 길이가 될 동안
   2. 현재 (+,-) [다음 탐색할 값] 이 target이면:
      1. answer+=1 한다
   3. 아니면 (현재 (+,-) [다음 탐색할 값] , 현재위치+1) 을 큐에 넣는다.

 

from collections import deque

def solution(numbers, target):
    answer = 0
    maxlen = len(numbers)
    q = deque()
    q.append((numbers[0],0))
    q.append((-numbers[0],0))

    while q:

        cur=  q.popleft()

        if cur[1]+1 < maxlen:
            if cur[0]+numbers[cur[1]+1] ==target and cur[1]+1 == maxlen-1:
                answer+=1
            else:
                q.append((cur[0]+numbers[cur[1]+1] ,cur[1]+1))

            if cur[0]-numbers[cur[1]+1]==target and cur[1]+1 == maxlen-1:
                answer+=1
            else:
                q.append((cur[0]-numbers[cur[1]+1] ,cur[1]+1))

    return answer