JavaScript로 선형 시간(O(n))에 두 수의 최대 곱 구하기

이번 글에서는 양수와 음수가 섞여 있는 숫자 배열을 입력받아, 배열을 단 한 번만 순회하여 두 수의 곱 중 최댓값을 반환하는 JavaScript 함수를 작성해 보겠습니다.

문제의 핵심 아이디어

최대 곱은 두 가지 경우에서 나올 수 있습니다.

• 가장 큰 양수 두 개의 곱
• 가장 작은 음수(절댓값이 큰 음수) 두 개의 곱 — 음수 × 음수 = 양수이므로 매우 클 수 있습니다.

따라서 배열을 한 번 순회하면서 최댓값 두 개(max1, max2)와 최솟값 두 개(min1, min2)를 동시에 추적하고, 마지막에 두 조합의 곱을 비교하면 O(n) 시간 복잡도로 답을 구할 수 있습니다.

예제 코드

const arr = [-1, -3, -4, 2, 0, -5];
const arr2 = [2, 3, 5, 7, -7, 5, 8, -5];

const produce = arr => arr.reduce((acc, val) => acc * val);

const maximumProduct = (arr = []) => {
    const [first] = arr;
    if (!first) {
        return 0;
    };

    const creds = arr.reduce((acc, val) => {
        const { min, max } = acc;

        if (val > max[0]) {
            max[1] = max[0];
            max[0] = val;
            return acc;
        };
        if (val < min[0]) {
            min[1] = min[0];
            min[0] = val;
            return acc;
        };
        if (val > max[1]) {
            max[1] = val;
            return acc;
        };
        if (val < min[1]) {
            min[1] = val;
            return acc;
        };

        return acc;
    }, {
        min: [first, first],
        max: [first, first]
    });

    const { max, min } = creds;
    return produce(max) > produce(min) ? produce(max) : produce(min);
};

console.log(maximumProduct(arr));
console.log(maximumProduct(arr2));

실행 결과

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

20
56

코드 동작 방식 설명

첫 번째 배열 [-1, -3, -4, 2, 0, -5]의 경우를 살펴보겠습니다.

• 가장 큰 두 수는 2와 0이므로 곱은 2 × 0 = 0
• 가장 작은 두 수는 -5와 -4이므로 곱은 -5 × -4 = 20
• 두 값을 비교하면 20이 최댓값입니다.

두 번째 배열 [2, 3, 5, 7, -7, 5, 8, -5]의 경우:

• 가장 큰 두 수는 8과 7이므로 곱은 8 × 7 = 56
• 가장 작은 두 수는 -7과 -5이므로 곱은 -7 × -5 = 35
• 두 값을 비교하면 56이 최댓값입니다.

reduce() 메서드를 활용해 누적 객체(acc) 안에 최댓값 배열 max와 최솟값 배열 min을 유지함으로써, 정렬 없이도 단일 순회만으로 원하는 값을 효율적으로 찾을 수 있다는 점이 이 알고리즘의 가장 큰 장점입니다.