JavaScript로 최대 쌍 합계 구하는 방법 완벽 가이드

문제 이해하기

길이가 2n인 정수 배열 arr를 첫 번째이자 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다.

함수의 목표는 이 정수들을 n개의 쌍, 즉 (a1, b1), (a2, b2), ..., (an, bn) 형태로 묶은 뒤, 모든 i에 대해 min(ai, bi)의 합이 최대한 커지도록 만드는 것입니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

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

그렇다면 기대되는 출력은 다음과 같습니다.

const output = 4;

출력 결과 해설

n은 2이며, 쌍을 (1, 2)와 (3, 4)로 나누면 각 쌍의 최솟값은 1과 3입니다. 따라서 최대 쌍 합계는 4 = min(1, 2) + min(3, 4)가 됩니다.

접근 방법

이 문제의 핵심 아이디어는 배열을 먼저 오름차순으로 정렬하는 것입니다. 정렬된 상태에서 인접한 두 요소를 하나의 쌍으로 묶으면, 각 쌍에서 버려지는 값(최댓값)의 손실을 최소화할 수 있습니다.

만약 큰 수와 작은 수를 무작위로 짝지으면, 큰 수가 쌍의 최솟값 역할을 하지 못하고 그대로 버려져 전체 합계가 줄어들게 됩니다. 따라서 정렬 후 0번째, 2번째, 4번째... 인덱스의 값을 더하면 곧 최대 쌍 합계가 됩니다.

구현 코드

다음은 위 로직을 구현한 코드입니다.

const arr = [1, 4, 3, 2];
const pairSum = (arr = []) => {
    arr.sort((a, b) => a - b)
    let sum = 0
    for (let i = 0; i < arr.length; i += 2) {
        sum += Math.min(arr[i], arr[i + 1])
    }
    return sum
}
console.log(pairSum(arr));

실행 결과

콘솔에는 다음과 같은 결과가 출력됩니다.

4

시간 복잡도 분석

정렬 단계에서 O(n log n)의 시간이 소요되며, 이후 순회는 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 추가적인 공간 사용 없이 제자리(in-place) 정렬을 활용하기 때문에 공간 복잡도는 O(1)로 매우 효율적입니다.