📖 문제링크
https://programmers.co.kr/learn/courses/30/lessons/43165
문제 설명
DFS 혹은 BFS로 푸는 문제이다.
필자는 DFS를 이용해 모든 경우의 수를 구하는 것으로 판단했다.
문제의 내용은 이렇다.
n개의 음이 아닌 정수가 있다. 그 정수들을 이용해 더하거나 빼서 타겟 넘버를 만든다.
타겟 넘버를 만드는 방법의 수를 return 하면 된다.
📃 조건
- 주어지는 숫자의 개수는 2개 이상 20개 이하이다.
- 각 숫자는 1이상 50 이하인 자연수다.
- 타겟 넘버는 1이상 1000 이하인 자연수다.
👨💻 문제풀이
필자가 푼 문제풀이
function solution(numbers, target) {
return dfs(0, numbers, target);
}
function dfs(startIndex, numbers, target) {
return (function cal(num, index) {
if (index === numbers.length) {
if (num === target) return 1;
return 0;
}
let first = num + numbers[index];
let second = num - numbers[index];
return cal(first, index + 1) + cal(second, index + 1);
})(0, startIndex);
}설명하자면 dfs는 깊이 우선 탐색 방법이기 때문에 원하는 sum 값을 받을 때까지 반복하는 재귀함수를 만들었다.
그리고 우리가 받은 numbers 배열의 index에 따라 +와 - 방식으로 반복하도록 했다.
여기서 return 1을 한 이유는 원하는 sum 값을 받을 때마다 1이 쌓이기 때문에 마지막 return에서는 모두 더해져서 나온다.
그리고 return안에 함수를 넣고 function cal(a, b) {}(a, b) 같이 즉시 실행 함수를 이용해 함수를 다시 선언하지 않고 바로 실행되도록 하였다.
🧐 다른 사람들의 코드
function solution(numbers, target) {
let answer = 0;
getAnswer(0,0);
function getAnswer(x,value) {
if(x<numbers.length){
getAnswer(x+1,value + numbers[x]);
getAnswer(x+1,value - numbers[x]);
} else{
if(value === target){
answer++
}
}
}
return answer;
}
필자보다 휠신 간단하게 나타내었다.
필자는 아무것도 없다면 0을 return한다고 나타냈지만 처음부터 0으로 선언해두면 된다는 것을 간과했다..(물론 방식이 달랐긴했지만ㅎㅎ)
돌아가는 로직에는 다른 점이 없는 것 같아 기분은 좋았다.
2022.01.26
backend-developer