[알고리즘] 프로그래머스 - 타겟 넘버(Python)

코딩테스트 연습 - 타겟 넘버 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

* 문제 설명

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 이하인 자연수입니다.

입출력 예

[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 문제라고 할 수 있다. 스택에 root 노드와 인덱스를 저장한 후 pop한 데이터를 다음 인덱스에  위치한 값과 더하거나 빼준다. 더한 값과 뺸 값은 스택에 다시 추가하여 pop할 수 있게 한다. 이 반복 과정은 스택이 전부 비워질 때까지 진행된다. 트리의 최대 깊이까지 계산을 진행했다면, 연산된 값과 target과 비교해준다. 연산된 값과 target이 같다면, answer를 1씩 증가시켜준다. 노드의 탐색이 끝났다면, answer를 return해준다. 

다음은 풀이 코드이다. 

def solution(numbers, target):
    answer = 0
    stack = [[numbers[0], 0], [-numbers[0], 0]]
    
    while stack :
        result_data, index = stack.pop() 
        index += 1
        
        # dfs 진행 -> append 순서 주의
        if index < len(numbers) :
            stack.append([result_data + numbers[index], index])
            stack.append([result_data - numbers[index], index])
        
        else :
            if result_data == target :
                answer += 1 
    
    return answer