문제?
한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.
한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.
요약:
정수 배열 요소 3개의 합이 0인 경우의 수를 리턴하는 함수 만들기.(값 중복 가능)
예시?
| number | result |
|---|---|
| [-2, 3, 0, 2, -5] | 2 |
| [-3, -2, -1, 0, 1, 2, 3] | 5 |
| [-1, 1, -1, 1] | 0 |
시도 과정!
function solution(number) {
var answer = 0;
var one= number[i]
var two= number.splice(i,1)
two.forEach
var three= two.splice(i,1)
for(let i =0; i<number.length; i++){
var sum += number[i]
sum=0? answer+1 : answer
}
return answer;
}내용이 빈약하지만 최대한 생각했던 원리를 반영하려고
노력한 흔적이다.
원래 내가 하려고 했던 구조의 조합 원리를 고민해보면,
예를 들어 [1,2,3]처럼
여러 개의 배열요소 중에서 3개를 뽑되,
5개의 배열요소가 있다면,
5x4x3의 경우의 수를 가진다.
다만 [1,1,1] 같은 중복은 되지만,
[1,2,3][1,3,2] [3,2,1].. 처럼 같은 요소의 반복은 안된다.
예를 들어 중학교 학생을 성적을 기준으로 3명을 뽑는다면
성적은 모두 같아도 학생들을 1번 학생 2번 학생 3번 학생,
2번 학생 3번학생 1번 학생을 뽑는 경우는 중복되는 경우의 수이다.
중복을 피하기 위해 3 x 2 x 1의 경우의 수로 나누면
60/6으로 10가지 경우만 남는다.
10가지가 와닿지 않아 직접 해보면
[1,2,3,4,5]라는 배열을 3가지 뽑는다면
1 [1,2,3]
2 [1,2,4]
3 [1,2,5]
4 [1,3,4]
5 [1,3,5]
6 [1,4,5]
7 [2,3,4]
8 [2,3,5]
9 [2,4,5]
10 [3,4,5]
정렬만 한다면 중복되지 않고 3가지씩 뽑을 수 있다.
#아쉽게도 ..
1시간이 넘어가서 내가 알고 있는 개념으로는 풀 수 없다고 생각이 들어
다른 팀원들의 답을 들어보기로 했다.
function solution(number) {
let answer = 0;
function dfs(start, curSum, count) {
if (count === 3) {
if (curSum === 0)
answer += 1;
return;
}
//dfs는 재귀함수로,
//start는 시작할 숫자를 선택하는 기능을 하는 '시작 인덱스'., i
//curSum은 현재까지 선택된 숫자들의 합, 0이면 1을 answer에 더함.
//count는 현재까지 선택된 숫자들의 개수, 3이면 재귀를 멈춤.
for (let i = start; i < number.length; i++) {
dfs(i + 1, curSum + number[i], count + 1);
}
}
// for문으로 모든 가능한 조합 탐색
//let i = start로 중복 선택 피하며 이전 선택한 숫자를 고르지 x
//dfs를 재귀적으로 호출하여 i+1부터 탐색 시작
dfs(0, 0, 0);
//start 0: 첫 번째 숫자부터 탐색
//cursum 0 : 합이 아직 없으므로, 초기값 0
//count 0 : 카운트 한 것이 아직 없으므로, 초기값 0
return answer;
}더 정확한 이해를 위해,
예시로 나와있는 [-2, 3, 0, 2, -5]를 통해 직접 풀어내고자 한다.
재귀함수의 순서를 좀 더 쉽게 보기 위해
문법을 떠나서
값을 구하는 절차상으로만 순서를 따지면,
dfs(0, 0, 0);
->
for (let i = start; i < number.length; i++) {
dfs(i + 1, curSum + number[i], count + 1);
}
}
->
if (count === 3) {
if (curSum === 0)
answer += 1;
return;
}
이런 순으로 보면 된다.
우선 첫번째 숫자부터 시작해서 초깃값부터 시작하여,
for문으로 +1로 그다음 요소부터 시작하게끔 하고
현재 0인 curSum에 0번째 숫자의 값을 더한다.
그럼 현재 0인 count에 첫번째 숫자를 카운트 해서 1을 더한다.
dfs(0,0,0)에서
dfs(1,-2,1)이 된 것이다.
그러면 다시
dfs(2,-2+3,2)
dfs(3,-2+3+0,3)
순으로 작동된다.
아쉽게도 첫번째의 합은 0이 되지 않아
if 문에서 +1이 되지 않는다.
그렇기 때문에 이전 호출로 돌아가
다시 dfs(2,-2+3+2,3)으로 진행한다.
값이 구해질 때까지 계속 재귀함수는 진행된다.
count가 3인 경우 삼총사 배열:
-2 3 0
-2 3 2
-2 3 -5
...
이러한 경우의 수에서
count가 3이되, (count는 삼총사 배열 요소의 수)
curSum이 0인 경우만 거르면 (cursum은 삼총사 배열 요소의 합)
-5 2 3
-2 0 2 으로
count가 2가 된다.
다시 시도해보기!
- 3개의 수를 중복되지 않게 고른다.
- 3개의 수를 모두 합한다.
- 0이 되는 경우를 +1하여 카운트 한다.
- 단, 중복되지 않도록 이전에 고른 수는 제외한다.
사실, 재귀함수는 위처럼 자세하게 뜯어보니 이해가 되는 정도이지만
아직 스스로 써본 적이 없어 익숙하지 않다.
for문으로 중첩되게 하여 쓰는 경우도 다른 팀원분들의 답에 있어
자세히 보지 않고 for문으로 써보려고 한다.
function solution(number) {
let answer = 0;
for(let i=0; i<number.length; i++){
var a= number[i]
}
for(let j=1; j<number.length-1; j++){
var b= number[j]
}
for(let k=2; k<number.length-2; k++){
var c= number[k]}
(a+b+c=0)? answer+1:answer
return answer;
}
실패 ===으로 바꿔줘야 하며 -2 -1 0 순으로 해야 중복x
최종 정답
function solution(number) {
let answer = 0;
const length = number.length;
for (let i = 0; i < length - 2; i++) {
for (let j = i + 1; j < length - 1; j++) {
for (let k = j + 1; k < length; k++) {
if (number[i] + number[j] + number[k] === 0) {
answer++;
}
}
}
}
return answer;
}
최종 정답이지만 이것도 다른 분의 답과 비슷해서
다음엔 시간이 좀 걸리더라도 답을 내야겠다 ㅠㅠ
