DFS/BFS: 타겟 넘버 [Lv2]
문제 설명
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 |
입출력 예 설명
문제에 나온 예와 같습니다.
Solution
내 풀이
def DFS(numbers, target, tot):
if len(numbers) == 0:
if tot == target:
return 1
else:
return 0
else:
res = 0
res += DFS(numbers[:-1], target, tot + numbers[-1])
res += DFS(numbers[:-1], target, tot - numbers[-1])
return res
def solution(numbers, target):
answer = DFS(numbers, target, 0)
return answer전형적인 DFS 문제이다.
나는 numbers에서 마지막 원소부터 시작하였고, 재귀함수 호출할 때 여태 더한 값을 넘겨줘야 할 것 같아서 파라미터가 하나 더 있는 DFS함수를 만들어 사용했다.
DFS함수를 호출할 때 마다 numbers에서 원소 하나씩 빠지며, numbers에 원소가 없으면 끝까지 다 실행한 것이므로 tot와 target을 비교하여 같다면 1, 같지 않으면 0을 리턴한다.
numbers의 원소를 더한 경우와 뺀 경우 두가지가 있기에, DFS함수를 두가지 방법으로 호출한다. 그리고 두번의 호출을 통해 받은 두 리턴값을 다시 리턴한다.
결과
Best Code
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])
solution을 호출할 때, numbers에서 빠지는 원소의 값만큼 target에서 빼거나 더하여 호출한다. 이로써 내가 풀이한 코드에서의 tot는 필요가 없어졌다.
내 코드에서 numbers의 원소의 부호가 +이면 tot에 더했는데, 이 코드에서는 target에서 빼는 방식이다. 따라서 numbers에 원소가 없고 target이 0이면 조건이 모두 만족한 것이다. 조건이 모두 만족하면 1을 리턴, 그렇지 않으면 0을 리턴한다.
numbers의 원소가 남아있다면 다시 재귀함수를 호출하는데, 원소값만큼 target에 빼는경우와 더하는경우 두가지를 호출하여 받은 리턴값들을 더하여 다시 리턴한다.
