문제
-
문제 설명
한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.
- 제한사항
3 ≤ number의 길이 ≤ 13
-1,000 ≤ number의 각 원소 ≤ 1,000
서로 다른 학생의 정수 번호가 같을 수 있습니다.
- 입출력 예시
| number | result |
|---|---|
| [-2, 3, 0, 2, -5] | 4 |
| [-3, -2, -1, 0, 1, 2, 3] | 2 |
| [-1, 1, -1, 1] | 0 |
나의 풀이방법
function solution(number) {
var answer = 0;
let sumArr = [];
for (let i = 0; i < number.length; i++) {
for (let j = i + 1; j < number.length; j++) { //중복 제거 방지로 인한 +i 보다 1 더한 만큼 시작
for (let k = j + 1; k < number.length; k++) { //마찬가지로 j 보다 1 더한만큼 시작
if (number[i] + number[j] + number[k] === 0) { //3가지의 요소 더한 값이 0이라면 answer + 1 해준다.
answer + 1;
}
}
}
}
console.log(answer);
}
내가 푼 풀이방법은 number의 배열에서 for 문을 돌릴때마다 인덱스 +1 자리부터 시작해서
중복되지 않게 해주고 i 부터 k 까지 3중 포문을 돌려서 number의 해당 인덱스를 더한 값이 0이라면 answer 을 +1 해주는걸로 풀었다.
재귀함수를 이용해서 문제풀이 방법
function solution(number) {
let result = 0;
const combination = (current, start) => {
if (current.length === 3) {
result += current.reduce((acc, cur) => acc + cur, 0) === 0 ? 1 : 0;
return;
}
for (let i = start; i < number.length; i++) { //5
combination([...current, number[i]], i + 1); //combination([-2],1) -2, [-2,3], 2 , [-2,3,0],3 [-2,3,2] 4, [-2,3,-5] ,5 result
}
}
combination([], 0);
return result;
}
solution([-2, 3, 0, 2, -5]);다른사람의 코드 풀이
많은 사람들이 재귀함수를 이용해서 문제를 풀어서 어떻게 이게 풀리는지를 직접 스택을 그려보면서 재귀함수를 이해해보았다 . 재귀함수는 함수안에서 함수를 호출해서 해당 조건이 만족될때까지 계속해서 함수가 실행되는 함수인데 재귀함수를 사용하기 위해서는 종료조건을 잘 설계해서 해줘야된다 아니면 콜스택이 무한대로 쌓이기 때문에 메모리에 부하가 올 수 있다고 한다. 해당 재귀함수에 대한 풀이를 해보겠다 . 먼저 combination([],0)으로 combination 함수를 호출했다. 실행이 되면서 if 문의 조건이 만족되지 않기 때문에 for loop 으로 빠진다 for 문은 start 가 number의 length 와 같아지면 멈추게 된다. number의 length 는 5이기때문에 절대 5를 넘을 수 없다. 재귀함수는 combination([],0) 이 호출되는 순간 콜스택에 combination[],1,combination [],2,combination[],3,combination[],4 실행이 예약된다. [],0 이 끝나는 순간 [],1 이 실행되는걸로 알고있으면 된다.
그럼 해당 코드를 보면서 콜스택에 메모리가 어떻게 들어가는지를 생각해보자.
- 콜스택 메모리
| combination | return | description |
|---|---|---|
| [],0 | ||
| [-2],1 | ||
| [-2,3]2 | ||
| [-2,3,0]3 | return | |
| [-2,3,2]4 | return | |
| [-2,3,-5]5 | return | [-2,3] 으로 돌 수 있는 모든 조건 종료로 인해 return 하여 [-2]2 시작 |
| [-2,0] 3 | ||
| [-2,0,2]4 | return | |
| [-2,0,-5]5 | return | [-2,0] 으로 돌 수 있는 모든 조건 종료로 인해 return 하여 [-2]3 시작 |
| [-2,2]4 | ||
| [-2,2,5]5 | return | [-2,2] 으로 돌 수 있는 모든 조건 종료로 인해 return하여 [-2]4 시작 |
| [-2,-5]5 | 종료 | start 변수가 5 되면서 number.length 와 같아지면서 종료 [],0 할 수 있는 모든 조건 끝나면서 콜스택에 예약되어있었던 [],1 이 시작됨. |
| [3] 2 | ||
| [3,0] 3 | ||
| [3,0,2] 4 | return | |
| [3,0,-5] 5 | return | [3,0] 으로 돌 수 있는 모든 조건 종료로 인해 return 하여 [3]3 시작 |
| [3,2] 4 | ||
| [3,2,-5] 5 | return | [3,2]로 돌 수 있는 모든 조건 종료로 인해 return 하여 [3]4 시작 |
| [3,-5] 5 | start 변수 5 되면서 for 문 종료 [],2 시작 | |
| [0] 3 | ||
| [0,2] 4 | ||
| [0,2,-5]5 | return | [0,2] 로 돌 수 있는 모든 조건 종료로 인해 return 하여 [0]4 부터 시작 |
| [0,-5]5 | 종료 | start 변수 5 되면서 for 문 종료 [],3 시작 |
| [2] 4 | ||
| [2,-5] 5 | 종료 | start 변수 5 되면서 for 문 종료 [],4 시작 |
| [-5] 5 | 종료 | 콜스택에 예약되었던 모든 combinaition 함수 종료되면서 해당 함수 종료됨. |
재귀를 이해하기 위해서는 모든 실행 스택들을 한번 그려본다면 재귀는 쉽게 이해할 수 있을거다. 나도 처음 재귀를 접하면서 왜 이게 이렇게 되지 ? 하면서 이해가 안됐는데 back tracking 같은 개념들을 찾아보고 친구한테도 물어보고 하면서 차근차근 하나하나 그려보니 이해가 됐다.
재귀함수를 이용해서 문제풀이 방법 2
function solution(number) {
let check = Array.from({ length: number.length }, () => false);
let result = 0;
const DFS = (idx, cnt) => {
if (cnt === 3) {
let SUM = 0;
check.map((v, i) => {
if (v === true) SUM += number[i];
});
result += SUM === 0 ? 1 : 0;
}
for (let i = idx; i < number.length; i++) {
if (check[i] === true) continue;
check[i] = true;
DFS(i, cnt + 1);
check[i] = false;
}
};
DFS(0, 0);
return result;
}