[DFS] 타겟 넘버 - Level 2 (프로그래머스)

타겟 넘버

문제 소개

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 함수를 작성해주세요.

시나리오

모든 경우를 다 확인해봐야하기 때문에 DFS나 BFS나 비슷할 것 같다. DFS 연습 겸 풀이했다.

1. numbers를 하나씩 순회하면서 양수일 경우와 음수일 경우를 고려해야한다.
2. 위의 예제에선 숫자를 다섯번만 더하거나 빼야하기 때문에 현재 몇번 연산하였는지 횟수와 현재까지의 합을 묶어서 스택에 push
3. 반복문은 stack이 비어지면 멈추고, 반복 시 pop하였을 때 연산횟수(n )이 numbers의 길이와 같다면 target과 비교한다.

문제 풀이

def solution(numbers, target):
    answer = 0
    stack = [[0,0]]

    while(stack):
        base, n = stack.pop()
    
        if n == len(numbers):
            if target == base: 
                answer += 1
            continue
        
        stack.append([base+numbers[n], n+1])
        stack.append([base-numbers[n], n+1])
    
    return answer