[프로그래머스] 삼총사 | JS

문제

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

해결 과정

function solution(number) {
    let answer = 0;
    number.sort((a,b) => a-b);
    // i는 첫 번째 숫자 (0부터 시작)
    for(let i = 0; i < number.length; i++) {
    //j는 i + 1 (즉, i 다음 숫자부터 시작)
        for(let j = i+1; j < number.length; j++) {
        // k는 j + 1 (즉, j 다음 숫자부터 시작)
            for(let k =j+ 1; k < number.length; k++) {
              if (number[i] + number[j] + number[k] === 0){
                  answer++;
              }  
            } 
        }
    }
    return answer;
}

 

삼중for문을 사용한 이유는 중복 없이 숫자를 선택할 수 있기에!

 

실패한 코드 ⬇️

테스트 코드에서 몇몇개가 실패했다. 오히려 위에서 삼중for문으로 하니까 잘되었는데..

그이유를 gpt한테 물어봤더니 중복된 값이 여러개 있을 때 조합 수를 정확하게 계산하지 못하는 문제가 있다고 한다..

이 문제는 3중 for문으로 해결해야 안전하고 정확하다고 한다. 

 

function solution(number) {
    let answer = 0;
    number.sort((a, b) => a - b);
    
    // i는 0부터 사용하여 첫 번째 숫자를 선택
    for (let i = 0; i < number.length - 2; i++) {
        if (i > 0 && number[i] === number[i - 1]) continue; // 중복 건너뜀
        // i가 선택된 후, 두 번째 숫자는 i + 1, 세 번째 숫자는 배열의 끝에서부터 시작
        let left = i + 1; 
        let right = number.length - 1;
        
        
        
        while (left < right) {
            
            let sum = number[i] + number[left] + number[right]; 

            if (sum === 0) {
                answer++;  
                left++;  // 중복 방지
                right--; // 중복 방지// 중복된 값 건너뛰기
        while (left < right && number[left] === number[left - 1]) left++;
        while (left < right && number[right] === number[right + 1]) right--;
            } else if (sum < 0) {
                right--;  // 합이 0보다 크면 더 작은 값을 찾아야 하므로 right 감소
            } else {
                left++;   // 합이 0보다 작으면 더 큰 값을 찾아야 하므로 left 증가
            }
        }
    }
    
    return answer;
}

 

투 포인터에 대한 설명

[알고리즘] 문제 해결 패턴 (2) 다중 포인터 패턴 — console.log("Hello, Bug!");

[알고리즘] 문제 해결 패턴 (2) 다중 포인터 패턴