프로그래머스 타겟 넘버 코드 및 해설 (파이썬)

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

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

 

먼저 numbers의 모든 숫자를 더한 값을 total로 놓고, total이 target과 같으면 모든 부호를 +로 하는 한 가지 방법밖에 없으므로 1을 반환합니다.
그 외의 total이 target보다 큰 경우엔 부호를 -로 바꿔야 하는 숫자들의 조합을 알아냅니다. total과 target의 차이를 2로 나눈 값을 diff_half로 놓고, numbers의 숫자 중 그 자체로 또는 여러 숫자의 조합으로 diff_half를 만들 수 있는 경우의 수를 구합니다. 이 경우의 수가 최종 답과 같으므로 이를 반환합니다.

 

 

from itertools import combinations

def solution(numbers, target):
    answer = 0
    # 내림차순으로 정렬 
    numbers.sort(reverse = True)
    
    # number의 총 합 
    total = sum(numbers)
    
    # 총 합이 target과 같으면 모두 더하는 한 가지 방법만 가능 
    if total == target:
        return 1 
    
    # total > target 
    diff_half = int((total - target) / 2)
    
    # diff_half 이하인 값들만 저장 
    minus = []
    for i in range(len(numbers)):
        if numbers[i] <= diff_half:
            minus = numbers[i:]
            break
    
    # minus의 값들 중 합쳐서 혹은 그 자체로 diff_half가 되는 경우의 수  
    for i in range(1, len(minus)+1):
        combs = combinations(minus, i)
        for comb in combs:
            if sum(comb) == diff_half:
                answer += 1 
        
    return answer