JavaScript로 배열에서 가장 큰 세 수의 곱(Triple Product) 찾기

이번 글에서는 정수 배열을 인자로 하나만 받는 JavaScript 함수를 작성해 보겠습니다.

함수는 입력으로 받은 배열을 바탕으로, 다음 조건에 따라 같은 길이의 새로운 배열을 만들어 반환해야 합니다.

문제 이해하기

출력 배열의 각 요소는 그 시점까지 등장한 숫자 중 가장 큰 세 수의 곱이어야 합니다. 다만 아직 세 개의 요소를 만나지 못한 경우, 즉 해당 인덱스가 3보다 작다면 그 자리에는 -1을 넣습니다.

곱을 계산할 때 값이 같은 숫자를 사용하는 것은 허용되지만, 반드시 서로 다른 인덱스에 있는 값이어야 한다는 점에 유의하세요.

예시

입력 배열이 다음과 같다고 가정해 봅시다.

const arr = [1, 2, 3, 4, 5, 6];

이때 기대되는 출력 결과는 다음과 같습니다.

const output = [-1, -1, 6, 24, 60, 120];

인덱스 0과 1에는 아직 세 개의 숫자가 없으므로 -1이 들어가고, 인덱스 2부터는 지금까지 본 가장 큰 세 수(1×2×3=6, 2×3×4=24, 3×4×5=60, 4×5×6=120)의 곱이 차례대로 저장됩니다.

구현 코드

이 문제는 길이 3짜리 배열에 현재까지의 최대값 세 개를 유지하면서, 새로운 요소가 들어올 때마다 내림차순으로 정렬한 뒤 가장 작은 값을 제거하는 방식으로 효율적으로 해결할 수 있습니다.

const arr = [1, 2, 3, 4, 5, 6];

const maximumTripleProduct = (arr = []) => {
    const res = [];
    // 현재까지 발견된 가장 큰 세 수를 관리하는 배열
    const max = [arr[0], arr[1], arr[2]];
    
    // 세 수를 만나기 전까지는 -1
    res[0] = res[1] = -1;
    res[2] = arr[0] * arr[1] * arr[2];
    
    for(let i = 3; i < arr.length; i++){
        max.push(arr[i]);          // 새로운 값 추가
        max.sort((a, b) => b - a); // 내림차순 정렬
        max.pop();                 // 가장 작은 값 제거
        res[i] = max[0] * max[1] * max[2]; // 상위 세 수의 곱
    };
    return res;
};

console.log(maximumTripleProduct(arr));

실행 결과

콘솔 출력 결과는 다음과 같습니다.

[-1, -1, 6, 24, 60, 120]

동작 원리 정리

이 알고리즘의 핵심은 다음과 같습니다.

첫째, 배열의 처음 두 위치에는 세 수의 곱을 만들 수 없으므로 -1을 배치합니다. 셋째 위치에서는 처음 세 요소의 곱을 바로 계산합니다.

둘째, 네 번째 요소부터는 새 값을 임시 배열에 추가한 후 내림차순으로 정렬하고, 길이를 3으로 유지하기 위해 마지막(가장 작은) 값을 제거합니다. 이렇게 하면 항상 현재까지의 최대값 세 개만 남게 됩니다.

셋째, 각 단계에서 남아 있는 세 수의 곱을 결과 배열에 저장하면 됩니다.

배열의 길이를 n이라 할 때, 매 반복마다 정렬이 수행되므로 전체 시간 복잡도는 O(n log n)입니다. 요소를 직접 비교하여 삽입 위치를 찾는 방식으로 개선하면 O(n)까지 최적화할 수도 있습니다.