Programmers _ 타겟 넘버 _ 파이썬

📃 문제

프로그래머스 타겟 넘버

알고리즘 - DFS

조건

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

💡 풀이 과정

1) DFS 🥳

cnt =0
def solution(numbers, target):
    nlen = len(numbers)
    
    def dfs(numbers, i,now, target):
        global cnt
        if i==nlen : 
            if target == now:
                cnt+=1
                return
            else:
                return
        dfs(numbers, i+1, now+numbers[i], target)
        dfs(numbers, i+1, now-numbers[i], target)

    dfs(numbers, 1, numbers[0], target)
    dfs(numbers, 1, -numbers[0], target)
    return cnt

처음 값 부터 양, 음 둘다 될 수 있으니 각각 호출로 시작해야한다

2) +,- 조합을 만들어서 더하기 (참고)

• 다른사람의풀이

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]		# [(4, -4), (1, -1), (2, -2), (1, -1)]
    s = list(map(sum, product(*l)))		# [8, 6, 4, 2, 6, 4, 2, 0, 0, -2, -4, -6, -2, -4, -6, -8]
    return s.count(target)

🔍 정리 & 배운 것

itertools
from itertools import product

리스트의 모든 조합을 구할 수 있다.
리스트에 *을 붙이면 각각 요소에서 갯수만큼 뽑아서 조합을 만든다

l = [(4, -4), (1, -1), (2, -2), (1, -1)]
print(list(product(l)))
# [((4, -4),), ((1, -1),), ((2, -2),), ((1, -1),)]

print(list(product(*l)))
# [(4, 1, 2, 1), (4, 1, 2, -1), (4, 1, -2, 1), (4, 1, -2, -1), (4, -1, 2, 1), (4, -1, 2, -1), (4, -1, -2, 1), (4, -1, -2, -1), (-4, 1, 2, 1), (-4, 1, 2, -1), (-4, 1, -2, 1), (-4, 1, -2, -1), (-4, -1, 2, 1), (-4, -1, 2, -1), (-4, -1, -2, 1), (-4, -1, -2, -1)]

여러개 뽑으려는 경우 : product(배열, repeat= 각 요소에서 뽑아낼 갯수)