문제 요약
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, 타겟 넘버 taget이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성하라.
제한사항
- 주어지는 숫자의 갯수는 2개 이상 20개 이하입니다.
- 각 숫자는 1 이상 50 이하인 자연수입니다.
- 타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
| numbers | target | return |
|---|---|---|
| [1,1,1,1,1] | 3 | 5 |
| [4,1,2,1] | 4 | 2 |
풀이 과정
처음 문제를 보고 생객하낸 풀이 방법은 DFS를 사용해서
1. numbers의 길이와 관계없이 가장 첫 번째 숫자가 처음 노드가 된다.
2. DFS를 두번 실행해야 한다. (+일 때, -일 때)
3. 각 결과에 대해서 target과 일치하면 count를 증가시킨다.
이 정도의 컨셉을 잡고 시작했지만, DFS라는 이름부터 보고 겁을 먹어서 그런지 풀이 방법을 떠올리지 못했고 이상한 코드를 만들고 있었다...
function solution(numbers, target) {
const graph = numbers.map((num, index) => [+num, -num]).filter((num,index) => index > 0)
const plusStart = +numbers[0];
const minusStart = -numbers[1];
// 재귀? DFS? BFS? 이진트리?...처음에는 numbers의 모든 숫자를 양수, 음수로 만들어서 배열 하나에 저장하고 [[1,-1],[2,-2]] 첫 번째 숫자의 양수로 DFS를 실행하고 음수로 DFS를 실행한다음 결과를 구하려고 했다.
이 상태에서 순회하는 방법을 만들려고 했으나 결국 실패하고 다른 사람의 코드를 참고 하였다.
function solution(numbers, length) {
let answer = 0;
dfs(0,0);
function dfs(level, sum) {
if(level === numbers.length) {
if(sum === target) {
answer += 1;
}
return;
}
dfs(level + 1, sum + numbers[level]);
dfs(level + 1, sum - numbers[level]);
}
return answer;
}어렵게 고민하던게 정답을 보고나니 쉽게 풀려버린 느낌이다.. depth를 의미하는 level 0부터 시작해서 계속해서 값을 더해나간다. 마지막 level일 경우 target과 비교해서 answer를 증가시킨다. 아닐 경우 다시 dfs를 재귀로 실행해서 계속해서 값을 구해나간다.
마무리
재귀가 필요한 문제를 만날때 마다 어려움을 느낀다. 어떻게 재귀를 풀어나갈 것인지 재귀함수를 어떻게 만들 것인지 아직 생각하는 능력이 부족하다...
