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

백준에서 ‘단계별로 풀기’를 통해 기본기를 쌓아왔는데, 이제는 주요 유형의 기본 문제들은 대부분 풀어본 것 같다. 그렇지만 아직 기초가 부족하다고 느껴서, 이번에는 프로그래머스의 ‘코딩테스트 고득점 Kit’를 풀어보려 한다. 기초를 다시 다지는 동시에 실제 코딩테스트와 가장 유사한 환경에도 적응해보는 것이 목표다.

난이도 : level 2
유형 : 완전탐색 , BFS
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3

문제

정수 배열 numbers와 목표값 target이 주어진다. 각 숫자 앞에 + 혹은 -를 붙여 식을 만들었을 때, 결과가 target이 되는 경우의 수를 구하는 문제다.

문제 접근

이 문제는 각 숫자마다 + 또는 -를 붙이는 두 가지 선택지가 존재한다. 따라서 완전 탐색할 경우 전체 경우의 수는 2^N가 된다.

N이 20 이하로 제한되어 있기에 보통 2^20 (약 100만) 까지는 완전탐색으로 충분히 풀 수 있기에 완전탐색으로 풀고자 했다.
방법은 BFS로 접근하였다.

(현재 인덱스, 현재 합) 형태의 상태를 큐에 넣고, 한 단계씩 차례대로 확장해나가면서 모든 경우의 수를 탐색할 수 있다.

해답 및 풀이

from collections import deque

def solution(numbers, target):
    q = deque()
    q.append((0, 0))  # (인덱스, 현재 합)
    count = 0
    n = len(numbers)

    while q:
        idx, cur_sum = q.popleft()

        # 모든 숫자를 다 사용한 경우
        if idx == n:
            if cur_sum == target:
                count += 1
            continue

        # 다음 숫자를 더하는 경우
        q.append((idx + 1, cur_sum + numbers[idx]))
        # 다음 숫자를 빼는 경우
        q.append((idx + 1, cur_sum - numbers[idx]))

    return count