문제
문제 설명
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 |
| [4, 1, 2, 1] | 4 | 2 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4총 2가지 방법이 있으므로, 2를 return 합니다.
풀이
dfs/bfs 아직 진짜 모르겠다 ㅜ.ㅜ
책 보면서 개념을 다시 익히고 구글링과 상욱슨의 도움을 받아 코드를 이해해보고 익히고자 했다!!!
dfs/bfs
- dfs: 스택이고 재귀함수를 사용한다
- bfs: 큐이고 deque을 사용한다
언제 dfs/bfs를 떠올리면 될까?
이진트리가 나오면 dfs/bfs를 떠올리자.
[1, 1, 1, 1, 1] 을 예로 들면
문제를 보면 +1, -1 로 가지치기를 하는 이진트리가 나온다.
그리고 무조건 5개를 다 써야 한다.
즉 완전 탐색하면서 이진트리 끝까지 다 내려가야 한다.
=> bfs/dfs와 어울리는 문제이군 !!
끝까지 내려가고 끝까지 내려갔을 때 결과값이 target과 똑같아야 한다는 종료조건이 매우 명확했다.
BFS로 풀어보다 안 되면 DFS로 풀어보자 <- 이 문제는 종료조건이 명확하고 BFS로 풀기 조금 까다로우니 DFS로 푸는 게 좋을 것 같다.
visited X -> 종료 조건이 필요하다
기본 dfs 함수처럼 visited 배열을 만들 필요가 없다. 절대 이전 노드를 방문할 일이 없기 때문!
쭉쭉쭉 더할 것이기 때문에 뒤로 돌아볼 필요가 없다.
그 대신 종료 조건을 설정해줘야 한다.
종료 조건 및 인덱스(depth) 설정
numbers의 길이를 DFS의 종료 조건으로 넣을 수 있다!!
depth를 numbers의 인덱스로 활용하기 위해
depth == len(numbers)로 설정
target과 일치하든 안 하든 무조건 종료해줘야 한다. depth가 그냥 종료 조건이다.
그렇기 때문에 종료 조건을 줘야해서 depth를 설정했다.
dfs 재귀함수
dfs를 두 방법 다 해줘야 한다. +, -
dfs(depth + 1, result + numbers[depth])
dfs(depth + 1, result - numbers[depth])
answer += 1
result == target 이면 방법 하나를 찾았다는 뜻이니까 answer += 1 해준다.
최종 코드
def solution(numbers, target):
n = len(numbers) # numbers 길이만큼 종료 지점 설정
answer = 0
def dfs(depth, result):
if depth == n: # 처음에는 depth가 0 이니 무조건 else로 간다.
if result == target: # 더하고 뺀 계산값이 목표값과 같으면
nonlocal answer
answer += 1 # 정답 처리 : 정답 개수 증가
return # 재귀 탈출 !
else: # 재귀함수 작성
dfs(depth + 1, result + numbers[depth]) # 한 depth 더 들어가서 더하거나
dfs(depth + 1, result - numbers[depth]) # 한 depth 더 들어가서 빼본다
dfs(0,0) # depth = 0 과 계산값 0 으로 초기화해서 시작
return answer