[프로그래머스][Python] 타겟 넘버 - 코팩

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

프로그래머스

문제

주어진 숫자에 + 혹은 -를 붙여서 원하는 숫자가 되게 만들 수 있는지 확인하고

만들 수 있다면 만들 수 있는 부호들의 조힙의 개수를 구해야한다.

 

평소에도 BFS알고리즘을 자주 사용하는 편이기에 문제를 풀 때도 BF를 이용해주었다.

덱(Deque)에 주어진 숫자들의 첫번째 숫자를 부호를 각각 +1, -1를 곱해주어서 넣어주었다.이후에 while문을 이용해서 조합을 구해주었다.

 

자세한 설명은 코드를 참고 부탁한다.

 

from collections import deque

def solution(numbers, target):
    answer = 0
    # 큐 생성
    queue = deque([])
    # 큐에 숫자가 담긴 리스트의 첫번째 숫자를 넣어준다.
    queue.append([numbers[0], 0])
    queue.append([-1*numbers[0], 0])
   
    while queue:
        total, index = queue.popleft()
        index += 1
        # 아직 모든 숫자에 부호를 부여하지 못했을 경우
        if index < len(numbers):
            queue.append([total + numbers[index], index])
            queue.append([total + -1*numbers[index], index])
   		
        # 모든 숫자에 부호를 부여했을 경우             
        else:
        # 모든 숫자들의 합을 합쳤을 경우 원하는 숫자가 나오는지 확인
            if total == target:
                answer += 1
            
    return answer