🧩 타겟 넘버
🎯 문제 설명
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 이하인 자연수입니다.
🙆🏻♀️ 문제 풀이
처음엔 DFS/BFS에 대해 공부를 하고 바로 풀어보게 된 문제라, 어떻게 해야 할지 갈피를 못잡았다😰.
분명 공부를 했음에도 그래서 어쩌라고..? 생각밖에 안들었다🤣🤣🤣.
일단 주어진 numbers에 각각 + 와 -를 붙여서 전부 구해야 겠다고 생각 했다.
가능한 모든 조합을 구한 다음 그 배열의 총 합이 target과 같은 수를 세는 거구나! 하고 깨달았다.
이를 그림으로 표현하면 다음과 같았다.
즉, [4, 1, 2, 1], [4, 1, 2, -1], [4, 1, -2, 1] ... 이런식으로 모든 조합을 구해서 각 배열의 합을 구해야 한다고 생각했다. (하지만 여전히 여기 어디에서 DFS/BFS 를 쓰라는 건지 모르겠었다😐.)
하지만 배열의 집합을 구하자니 4중 for문 밖에 답이 나오지 않았다...🤯 구글링을 한 결과 경우의 수를 배열로 구하는 게 아니라 트리를 타고 내려오면서 합한 결과 값으로 트리를 그려야 함을 알아냈다!
그림으로 표현하면 이렇게 된다. 여기서 가장 아랫줄에서 target과 같은 수를 찾아서 갯수를 세면 된다.
코드로 짜려고 생각해보면 주어진 numbers배열을 돌면서 숫자마다 +한 숫자와, -한 숫자를 배열안의 숫자에 더해주고 더해주면서 늘려나가야 한다.
- 경우의 수를 담는
cases배열을 만들고,numbers를 돌면서 그 안에서 임시 배열(temp)안에 먼저 첫번째 요소인4에 대해+,-한[+4, -4]를 담는다. temp배열을 cases에 재할당해준다. - 그 다음 요소인
1부터는 루프 내부에서 cases를 루프로 돌면서4와-4에 각각+,-한 요소를 더한 임시배열을 만들어 cases에 재할당 해준다. - 해당과정을 반복하는 그림을 그리면 다음과 같다.
😳 가능한 모든 새로운 합산값을 구해 배열에 저장하고 cases에 재할당하는 과정이 BFS 과정에 해당한다.
(cases 가 queue 역할을 하고 있다.)
🕶️ 최종 BFS 코드
// ver 1
function solution(numbers, target) {
let count = 0;
function bfs() {
// 처음 합산값은 0 으로 초기화해준다.
let cases = [0];
// numbers 배열을 돌면서
for (let i of numbers) {
const temp = [];
// cases 에 들어있는 합산값과 numbers의 수를 +, - 해서 임시배열에 넣고
for (let j of cases) {
temp.push(j + i);
temp.push(j - i);
}
// 임시배열을 cases로 업데이트해준다.
cases = temp;
}
// 최종적으로 숫자 4개를 더한 값만 있는 배열을 반환한다.
return cases;
}
// bfs를 호출해 합산값의 배열을 받아온다.
const cases = bfs();
// 합산값의 배열을 돌며 target과 같은 수를 발견하면 count 해준다.
for (let i of cases) {
if (i === target) count++;
}
return count;
}
//----------------------------------//
//ver 2
function solution(numbers, target) {
let cases = [0];
for(let i of numbers){
const temp = [];
for(let j of cases){
temp.push(j + i);
temp.push(j - i);
}
cases = temp;
};
let count = 0;
for(let i of cases){
if(i === target) count++;
};
return count
}🕶️ DFS 코드
BSF가 되면 DFS도 된다!!
function solution(numbers, target) {
let count = 0;
function dfs(idx, curVal) {
// 만약 인덱스가 numbers배열의 길이와 같고 === 4가지 숫자를 모두 사용했는데
if (idx === numbers.length) {
// 현재 값이 target과 같다면
if (curVal === target) {
// count를 센다.
count++;
}
return;
}
// 재귀적으로 dfs를 호출하면서 idx(depth)를 늘리고, numbers에서 늘어난 idx에 해당하는 수를 +, - 해준다.
dfs(idx + 1, curVal + numbers[idx]);
dfs(idx + 1, curVal - numbers[idx]);
};
// 맨 처음 dfs 호출시에는 0번째 인덱스와 합산값으로 0(init)을 넣어준다.
dfs(0, 0);
return count;
}