[프로그래머스] 삼총사 (Javascript)

문제

프로그래머스

요구사항
한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 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]	2
[-3, -2, -1, 0, 1, 2, 3]	5
[-1, 1, -1, 1]	0

 

내가 생각한 로직

처음에 생각한 로직

1. reduce 메서드로 배열의 전체 합을 구한다.

2. 전체 합에서 (배열의 전체 길이 - 3)개의 요소들의 합을 뺐을 때, 0이 되는 순간을 구한다.

3. count 변수를 만들어서 그 순간마다 count에 1을 더한다.

 

🚨 배열의 길이가 정해져있는 것이 아니기 때문에, 배열의 길이마다 숫자를 더해줘야 하는 방법을 고려해야 한다.

 

두 번째로 생각한 로직

1. for문을 3개 이용해서 배열의 요소에 3개까지 접근하게 만들기

2. i < j < k일 때 3개 숫자의 합을 구한다. (중복되는 경우를 제거하기 위해)

3. count 변수를 만들어서 합이 0일 때 count에 1을 더한다.

 

반복문을 이렇게 많이 써도 되나 싶어서 자신이 없었지만,

코드를 작성해 본 결과, 테스트를 통과하였다.

 

 

내가 구현한 코드

01 전체 합에서 (배열의 전체 길이 - 3)개의 요소들의 합을 빼면 0일 때 구하기 ❌

function solution(number) {
    const sum = number.reduce((acc, cur) => acc + cur);
    let count = 0;
    
    for(let i = 0; i < number.length; i++) {
        for(let j = 0; j < number.length; j++) {
            if (i !== j && i < j) {
                let twoSum = number[i] + number[j];
                console.log(twoSum);
                if (sum - twoSum === 0) count += 1;
            }
        }
    }
    return count;
}

🚨 첫번째 예시만 보고 코드를 짜고 다른 예시들을 고려하지 않고 짰었다.

배열의 전체 길이를 5라고만 생각하고 짰기 때문에, 첫 번째 예시를 제외하고는 나머지가 통과할 수 없었다.

이 로직에서 벗어나 다시 본점으로 돌아갔다.

 

 

02 3개의 for문 이용하기 ✅

function solution(number) {
    let count = 0;
    
    for (let i = 0; i < number.length; i++) {
        for (let j = 0; j < number.length; j++) {
            for (let k = 0; k < number.length; k++) {
                if (i < j < k) {
                    if (number[i] + number[j] + number[k] === 0) count += 0;
                }
            }
        }
    }
    return count;
}

이 로직이 맞는 것 같은데 왜 안되는지 이유를 모르겠어서 한참을 들여다보고 있었다.

&&로 조건문을 작성하는게 익숙하지 않아서 그런가 대놓고 잘못된 조건식을 작성하고 있었다.

 

if (i < j < k)

이렇게 작성하니 작동할리가 없었다.

 

if (number[i] + number[j] + number[k] === 0) count += 0;

게다가 count에 1을 더해줘야 되는데 0을 더하고 있었다.

 

 

function solution(number) {
    let count = 0;
    
    for (let i = 0; i < number.length; i++) {
        for (let j = 0; j < number.length; j++) {
            for (let k = 0; k < number.length; k++) {
                if (i < j && j < k) {
                    if (number[i] + number[j] + number[k] === 0) count += 1;
                }
            }
        }
    }
    return count;
}

조건식을 논리합 연산자(&&)로 수정해주고 count에 1을 더하는 로직으로 코드를 바꾸면 정상적으로 작동한다.

 

 

다른 해결방법

사용한 도구: combination 함수 제작, 재귀 함수 이용

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++) {
            combination([...current, number[i]], i + 1);
        }
    }
    combination([], 0);
    return result;
}

 

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++) {
    combination([...current, number[i]], i + 1);
  }
};

 

배열의 길이가 3일 때 배열의 전체 합을 구하고, 합이 0이면 1을, 0이 아니면 0을 반환하는 함수를 제작하였다.

combination 함수로 들어가는 인자는 current와 start가 있다.

current = 현재까지 선택된 숫자 리스트

start = 탐색을 시작할 인덱스 (중복 선택 방지)

 

for (let i = start; i < number.length; i++) {
    combination([...current, number[i]], i + 1);
}

[]
├── [-2] (i = 0)
│   ├── [-2, 3] (i = 1)
│   │   ├── [-2, 3, 0] → 합: 1 (X)
│   │   ├── [-2, 3, 2] → 합: 3 (X)
│   │   ├── [-2, 3, -5] → 합: -4 (X)
│   ├── [-2, 0] (i = 2)
│   │   ├── [-2, 0, 2] → 합: 0 ✅ (result += 1)
│   │   ├── [-2, 0, -5] → 합: -7 (X)
│   ├── [-2, 2] (i = 3)
│   │   ├── [-2, 2, -5] → 합: -5 (X)
├── [3] (i = 1)
│   ├── [3, 0] (i = 2)
│   │   ├── [3, 0, 2] → 합: 5 (X)
│   │   ├── [3, 0, -5] → 합: -2 (X)
│   ├── [3, 2] (i = 3)
│   │   ├── [3, 2, -5] → 합: 0 ✅ (result += 1)
├── [0] (i = 2)
│   ├── [0, 2] (i = 3)
│   │   ├── [0, 2, -5] → 합: -3 (X)

재귀 호출의 흐름은 다음과 같다.

재귀 함수를 이용해서 배열의 길이가 3인 경우를 모두 찾은 뒤, 합이 0인 경우를 확인한다.

 

나는 함수 내에서 또 다른 함수를 제작할 생각을 하지도 못했고, 재귀 함수를 사용하는 방법도 몰랐다,

재귀 함수 때문에 이 코드를 이해하는데도 많은 시간이 걸렸다..