[프로그래머스] 타겟 넘버 / Python / 순열과 조합

타겟 넘버

• 문제
  사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

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

나의 풀이

• 효율적으로 완전 탐색을 구현하려고 했다.

def solution(numbers, target):
    answer = 0
    # 첫번째 숫자를 가져와 (-, +) 부호로 나누어 시작
    current_list = [numbers[0], -numbers[0]]
    for i in range(1, len(numbers)):
        next_num = numbers[i] # 다음 숫자
        next_list = []
        for c in current_list: # 현재 리스트에 있는 숫자들에 다음 숫자를 더하거나 빼서 저장
            next_list.append(c + next_num)
            next_list.append(c - next_num)
        current_list = next_list # 리스트 업데이트
    
    for x in current_list:
        if x == target:
            answer += 1
        
    return answer

다른 풀이

• itertools.product로 두 개 이상의 리스트의 모든 조합을 간편히 구할 수 있다.
• 훨씬 쉽고 간결한 풀이

from itertools import product

def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)