[프로그래머스] Level2 - 타겟넘버*

문제 설명

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

---

나의코드(풀이를 참고한 코드)

def solution(numbers, target):
    result = 0 
    def dfs (num, level):
        nonlocal result
        
        if level==len(numbers):
            if num==target:
                result+=1
            return
            
        signal=[-num,num]
        if level==1:
            for s in signal:
                dfs(s+numbers[level],level+1)
                dfs(s-numbers[level],level+1)
        else:
            dfs(num+numbers[level],level+1)
            dfs(num-numbers[level],level+1)
            
    dfs(numbers[0],1)
    
    return result

결국 난 이 문제를 해결해내지 못했고 DFS로 푼 가장 직관적인 코드라 생각하여 참고하고 이를 이해하고 다시 작성해보았다.

DFS구현은 결국은 재귀함수를 사용하는 것이다. 재귀함수를 풀어보면 결국은 DFS가 된다. 재귀함수를 사용하는게 어떻게 보면 우리의 생각의 흐름대로 짤 수 있는 가장 단순하면서 나에게 가장 어려운 방식이다... 재귀로 푸는건 정말 너무 어렵다 ㅠㅠㅠㅠ

 

위의 코드 내용은 단순하다. numbers의 첫번째 수부터 그 다음 수를 차례대로 더해보고 빼보는 거다. 그러고 최종적으로 나온 결과값이 target과 일치하면 result+=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])

해당 코드는 정말 참고만하기 위한 코드이다. 정말 그냥 대단하다는 생각밖에 안드는 코드이다... 내가 이렇게 문제를 풀 수 있을까하는 생각도 든다...허허 

이 코드를 해석해보면 결국 target을 계속 깍아나가는 것이다. 그렇게 numbers를 다 사용했을 때 target이 0이라면 이는  타겟넘버를 맞추는 식이기때문에 return 1을 하고 그렇지 않다면 return 0을 한다. 그렇게 모여진 1,0을 모두 더하여 최종 경우의 수를 구하는 것이다.

정말 그냥 아름답다...

 

 

---

nonlocal

nonlocal : 지역변수가 아님을 선언 -> nonlocal이 사용된 함수 바로 앞단계의 함수에서 지역변수로 선언된 변수 사용

x = 20 # 전역변수

def f():
    x = 40
    
    def n():
        nonlocal x
        x = 80
        
    n()  # 함수 n를 실행하여 nonlocal이 적용되도록 한다.
    print(x)  # 함수 f에서의 x값이 출력된다. 
f()
print(x) # 전역변수가 그대로 print
--------------------------------------------------------
80
20