[프로그래머스] 타겟 넘버 (Python)

lemonlily·2024년 1월 18일

문제

문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

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

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

입출력 예
numbers target return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

총 2가지 방법이 있으므로, 2를 return 합니다.

문제 풀이 접근

DFS/BFS 카테고리 문제라서 처음 접근은 DFS로 끝까지 모든 숫자를 더한 뒤에 target과 같으면 answer를 하나씩 올려주는 방식을 사용하려고 했다. (재귀 함수 방식)
그러나 조금 색다르게 접근해봐도 좋겠다고 생각을 했는데, 결국 완전 탐색이다 보니까 전체 numbers 인덱스 중에서 양수인 인덱스를 조합으로 뽑아내고, 나머지는 음수로 해서 다 더하는 것과 동일할 수 있겠다고 생각했다.
특히 주어지는 숫자의 개수가 20개 이하라서 매우 짧기 때문에 새로운 코드로 시도해보고자 했다.
그래서 두가지의 방식으로 접근해서 문제를 풀어봤다.

정답 코드 (combinations)

from itertools import combinations

def solution(numbers, target):
    answer = 0
    
    pos = [i for i in range(len(numbers))]
    
    for i in range(1, len(pos)+1):
        pos_idx = list(combinations(pos, i))
        
        ## 개수별 조합에 대하여  
        for j in pos_idx:
            hap = 0
            for k in range(len(numbers)):
                if k in j:
                    hap += numbers[k]
                else:
                    hap -= numbers[k]
            if hap == target:
                answer +=1  
        
    
    return answer

pos는 인덱스 배열이다. 양수가 될 인덱스를 뽑아낼 것이기 때문에 이름을 pos로 했다.
pos_idx 는 예를 들어 numbers의 길이가 5라면, nubmers 중 1개만 positive일 때의 인덱스 조합, 2개만 positive일 때의 인덱스 조합... (경우의 수) 가 뽑히도록하였다.
따라서 개수별 양수 조합 (j)에 대하여, numbers의 인덱스(k)들을 하나씩 비교하면서 k가 j에 있을 때 (즉, k번째 숫자는 양수일 때) 는 더하고, 아닐 때는 빼는 방식으로 접근했다.
삼중 for 문을 사용하는 방식이지만 20개 이하의 배열에 사용되기 때문에 간편하게 구현할 수 있다는 장점이 있었다.

정답 코드 (DFS)

    
def solution(numbers, target):
    
    def check(idx, local_hap):
        nonlocal answer
    
        if idx == len(numbers):
            if local_hap == target:
                answer += 1
            return 
    
        check(idx+1, local_hap+numbers[idx]) ## 더해주는 경우
        check(idx+1, local_hap-numbers[idx]) ## 빼주는 경우 
    
    
    answer = 0 
    check(0, 0)

    return answer