[JavaScript] 삼총사 - 프로그래머스

문제 :

 

 

내 풀이 : 

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

 

• 첫 번째 반복문 (i): 배열 number의 첫 번째 요소부터 시작한다.
• 두 번째 반복문 (j): i보다 뒤에 있는 요소들 중 하나를 선택한다.
• 세 번째 반복문 (k): j보다 뒤에 있는 요소들 중 하나를 선택한다.

이 세 개의 반복문은 배열 내에서 서로 다른 세 개의 인덱스 i, j, k를 선택해 조합을 만든다.

 

선택된 세 숫자 number[ i ], number[ j ], number[ k ]의 합이 0인지 확인하고, 합이 0인 경우 cnt를 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++) {
            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);
    }
}

 

combination 함수는 현재 조합된 숫자들을 저장하는 current 배열과, 배열의 시작 인덱스 start를 인자로 받는다.

 

 

기저 조건 :

if (current.length === 3) {
    result += current.reduce((acc, cur) => acc + cur, 0) === 0 ? 1 : 0;
    return;
}

 

이 부분에서는 현재 조합된 숫자가 3개인지를 확인한다.

만약 3개라면, 이 세 숫자의 합이 0인지 확인하고, 조건을 만족하면 result를 1 증가시키고 함수는 종료된다. 

 

 

재귀 호출 :

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

 

이 반복문은 주어진 배열 number에서 start 인덱스부터 시작해 하나씩 숫자를 추가하며, 새로운 조합을 생성한다. combination 함수를 재귀적으로 호출하여 숫자를 current 배열에 추가하고, start 인덱스를 1 증가시켜 다음 요소를 선택하도록 한다.

 

 

함수 호출:

combination([], 0);

 

초기에는 빈 배열 []과 시작 인덱스 0으로 combination 함수를 호출한다. 모든 가능한 세 숫자 조합을 생성하게 된다.

 

 

 

 📌 위 풀이도 세 숫자를 선택하는 모든 조합을 검사하므로 배열의 크기가 커질수록 실행 시간이 증가할 거라고 생각했다.

 

 

검색해 보니 일반적으로 사용되는 방법 중 하나는 정렬과 투 포인터(Two-pointer) 기법을 사용하는 것이다.

 

투 포인터(Two-pointer)기법은 배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용하여 문제를 효율적으로 해결하는 방법이다.

 

주로 정렬된 배열에서 특정 조건을 만족하는 부분 배열이나 쌍을 찾을 때 사용된다. 이 기법은 두 포인터를 배열의 서로 다른 위치에 두고, 조건에 따라 포인터를 이동시키며 문제를 해결한다.

• 정렬된 배열에서 특정 합을 찾는 문제
• 두 배열 간의 합을 찾는 문제
• 부분 배열의 길이를 최적화하는 문제

위와 같은 문제에 효과적이다.

 

 

📌 하지만 위 문제는 입력 배열이 정렬되지 않은 상태에서도 동작해야 하고, 모든 조합을 다 확인해야 하기 때문에 간단하고 정확한 해결 방법은 3중 루프를 사용하는 것이 맞았다!

 

 

다음에 투 포인터(Two-pointer)기법을 사용하여 풀면 가장 효율적일 문제를 풀게 된다면 그때 적용시켜 봐야겠다.