프로그래머스 [lv2] 타겟넘버 파이썬

포인트

1. 리스트 내 원소는 모두 같다.
2. 타겟 넘버를 맞추는 방법이 ** 몇가지** 인지만 알면 된다.

전형적인 재귀 문제로, dfs를 이용하여 풀 수도 있지만, itertools라이브러리의 product메소드를 사용하여 pythonic한 코드를 작성할 수도 있다.

풀이 1) product, 곱집합

from itertools import product

def solution(numbers, target):
    temp = [(i, -i) for i in numbers]
    result = [1 for i in product(*temp) if sum(i) == target]
    return len(result)

temp 를 출력하면

temp = [(i, -i) for i in numbers]
print(temp)

>>> [(1, -1), (1, -1), (1, -1), (1, -1), (1, -1)]

product를 사용하여 temp 원소들의 곱집합을 출력하면 전체 경우의 수가 출력된다.

for i in product(*temp):
    print(i)

>>> (1, 1, 1, 1, 1)
(1, 1, 1, 1, -1)
(1, 1, 1, -1, 1)
(1, 1, 1, -1, -1)
(1, 1, -1, 1, 1)
(1, 1, -1, 1, -1)
...

=> 총 32가지 

이 32가지 경우의 집합 중, 집합의 총합이 target과 같은 집합의 갯수를 고르면 된다. (어떤 집합이 타겟을 맞추는지는 상관없다)

리스트 컴프리헨션으로 조건의 맞는 경우 1을 리턴하여 result 리스트에 저장하고, result 리스트의 길이를 답으로 출력.

풀이 2) DFS, 재귀

result = 0

def solution(numbers, target):
    global result

    dfs(0, numbers, target, 0)
    return result

def dfs(idx, numbers, target, curr):
    N = len(numbers)
    global result
    if idx == N and curr == target:
        result += 1
        return
    if idx == N:
        return

    dfs(idx + 1, numbers, target, curr + numbers[idx])
    dfs(idx + 1, numbers, target, curr - numbers[idx])

궁금점

• DFS 풀이에서, numbers[idx] 부분에 idx 대신 0을 넣으니 에러가 났다.
• 모든 리스트의 원소가 같으니 당연히 idx 대신 0을 넣어도 상관없다고 생각했는데, idx를 넣으니 통과, 0을 넣으니 에러가 발생했다.
• 이유를 아시는 분은 댓글 부탁드립니다 :) ㅠ