#24 [파이썬] 프로그래머스: 타겟 넘버

<문제>

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

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

---

 

<소스코드>

def solution(numbers, target):
    answer = 0
    def dfs(i, sum):
        nonlocal answer
        if i == len(numbers) and target == sum:
            answer += 1
            return
        if i == len(numbers):
            return
        dfs(i + 1, sum + numbers[i])
        dfs(i + 1, sum - numbers[i])
    dfs(0, 0)
    return answer

 

※ 다른 사람 풀이 1

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

※ 다른 사람 풀이 2

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

---

 

<NOTE>

■ nonlocal과 global 차이점: nonlocal은 내부함수에서 외부함수의 변수를 접근하기 위해서 언급하는 것이고, global은 함수 내부에서 전역변수에 접근하기 위해서 언급하는 것이다.

 

■ 첫 요소부터 부호가 + 또는 - 가 될 두 가지 경우의 수를 고려하여 그 다음 요소도 마찬가지로 + 와 - 두 가지를 생각하면서 재귀적으로 계산해나간다. 작은 문제를 해결함으로써 큰 문제를 해결하는 방식이다.

 

■ dfs의 인자로 들어가는 i와 sum에서 첫번째 요소에도 부호의 두 가지 경우를 반영하기 위해 sum을 0으로 설정하고 돌려서 i=0일 때 실행되는 재귀에서 sum의 값을 두 가지 경우로 업데이트 하도록 한다. 말하고자 하는 것은 i는 numbers의 index가 아니라 단순히 재귀를 반복하는 실행 수일 뿐이고, 종료 조건을 구성할 때 실제로 sum이 업데이트 되는 횟수에 초점을 두어야 한다. i = 1부터 sum에 유의미한 숫자가 들어갔으므로 1부터 numbers의 길이인 5까지 5번 업데이트 되면 끝낸다. >>> 종료 조건이 i == len(numbers) - 1이 아닌 i == len(numbers) 의 이유 <<<

 

■ 재귀의 종료 조건 고민하기: 결국 마지막 요소까지 더했을 때 그 값이 3이거나 아니거나 둘 중 하나이다. 따라서 마지막 요소 i == len(numbers) 이면서 그 값이 타겟 넘버 target == sum 이거나, 그렇지 않고 그냥 마지막 요소 i == len(numbers) 이면 종료할 수 있도록 설정한다.