[알고리즘 연습] 타겟 넘버 (프로그래머스 lv2, 파이썬)

문제

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

코딩테스트 연습 - 타겟 넘버

풀이

from collections import deque

def solution(numbers, target):
    que = deque([0])
    for i in range(0, len(numbers)):
        for _ in range(2**i):
            now = que.popleft()
            que.append(now + numbers[i])
            que.append(now - numbers[i])
    return que.count(target)

• 값을 하나씩 넣어가며 BFS를 수행하는 방법이다.
• deque를 사용하지 않고 list.pop(0)를 사용할 경우 두개의 케이스에서 시간이 초과된다.

def solution(numbers, target):
    if len(numbers) == 1:
        if target-numbers[0] == 0 or target+numbers[0] == 0:
            return 1
        else:
            return 0
    return solution(numbers[1:],target-numbers[0]) + solution(numbers[1:],target+numbers[0])

• 재귀를 통한 해결방법이다.
• 각 값을 target에서 더하고 빼주면서 최종적으로 target이 0이 되는 경우의 횟수를 더한다.