[Python/Programmers] 타겟 넘버

문제

1. 난이도: 프로그래머스 Level 2

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

3. 문제핵심: DFS

• numbers 배열에 주어진 모든 수를 더하거나 빼서 target과 같은지 확인해야 하므로 모든 경우의 수를 탐색해야 한다.
• 이때 각 순간마다의 합한 결과에 다음의 인덱스 값을 더해줘야(혹은 빼줘야)한다.

내 코드

1. 첫 번째 아이디어(대실패)

2. 두 번째 아이디어

• 리스트에 지금까지의 합한 결과를 저장하자

def solution(numbers, target):
    answer = 0
    stack = list()
    stack.append([numbers[0], 0])
    stack.append([-numbers[0], 0])
    while stack:
        temp, index = stack.pop()
        index += 1
        if index < len(numbers):
            stack.append([temp+numbers[index], index])
            stack.append([-(temp+numbers[index]), index])
            
        else:
            if temp == target:
                answer +=1
    return answer

• index 값을 같이 저장해서 다음 인덱스 값과 더해주거나 빼준다.

이상 코드(재귀함수 버전)

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
            
    dfs(0,0)
    return answer

• 출처: (https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS)
• nonlocal: "지역변수는 아닌 변수"
• 현재 answer가 전역변수로 지정되어 있지 않고 solution이라는 함수의 지역변수로 지정되어 있으므로
• dfs 함수에서 answer를 사용해주기 위해서는 nonlocal 키워드를 사용해 다른 범위에 있는 변수를 사용해야 한다.