문제 설명
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 이하인 자연수입니다.
입출력 예
| numbers | target | return |
| [1, 1, 1, 1, 1] | 3 | 5 |
이번 문제는 재귀함수를 이용한 DFS로 풀 수 있을거라는 생각이 들었다.
아래 그림과 같이 재귀 함수를 시작하여 +1, -1 을 각각 호출하여 numbers의 마지막 숫자까지 더해진 값이 target과 같으면 count를 증가시켜 count값을 리턴하는 형태로 풀고자 하였다.
하지만 예상치 못했던 파이썬 문법 문제에 직면하였다. 파라메터로 전달된 count의 값을 함수 내부에서 증가시켜도 밖에서는 count값이 증가되지 않았던 것이다. 아마 지역변수, 전역변수의 문제인 것 같아 이런 저런 시도를 해보았지만 실패하였고 결국 구글링을 했다.
파이썬에서 전역변수를 사용하려면 함수를 호출하는 부분에서, 그리고 함수 내부에서도 global이라는 전역변수 지정을 해줘야 했던 것이다.
(파이썬에서는 함수 내부에서도 global 선언을 해주지 않으면 지역변수처럼 사용된다)
그리고 global a = 0 로 전역변수 지정과 초기화를 동시에 작성하여도 에러가 났다.
나의 풀이
def solution(numbers, target): answer = 0 depth = 0 global count count = 0 go(numbers, target, depth, answer) return count def go(numbers, target, depth, answer): global count if depth == len(numbers): if answer == target: count += 1 return else: return go(numbers, target, depth+1, answer-numbers[depth]) go(numbers, target, depth+1, answer+numbers[depth])
함수 외부에서 count = 0로만 선언하고, 함수 내부에서 nonlocal count라고 지정해 주어도 위 코드와 같게 동작된다.
다른 사람의 풀이
아래 블로그에서는 dfs, bfs를 사용하여 문제를 풀었다. 이런 방법도 숙지하도록 해야겠다.
