JavaScript로 정렬된 두 배열에서 합이 가장 작은 쌍 찾기

문제 이해하기

정렬된 두 개의 정수 배열 arr1과 arr2를 각각 첫 번째, 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.

세 번째 인수는 숫자 num이며, num은 항상 두 배열의 길이보다 작은 값입니다. 함수의 목표는 정확히 num개의 정수 쌍(pair)을 선택하는 것입니다.

각 쌍의 첫 번째 요소는 arr1에서, 두 번째 요소는 arr2에서 가져와야 하며, 선택된 쌍들은 가능한 한 가장 작은 합을 가져야 합니다. 최종적으로 함수는 이렇게 선택된 num개의 쌍을 배열 형태로 반환합니다.

예를 들어, 함수에 다음과 같이 입력이 주어진다면 —

const arr1 = [1, 1, 2];
const arr2 = [1, 2, 3];
const num = 2;

출력은 다음과 같아야 합니다 —

const output = [
    [1, 1], [1, 1]
]

접근 방식

이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다. arr1의 각 요소가 arr2에서 어느 위치까지 탐색했는지 추적하는 포인터 배열(temp)을 유지하면서, 매 단계마다 현재 만들 수 있는 쌍 중에서 합이 가장 작은 것들을 선택하는 원리입니다.

동일한 최소 합을 가지는 여러 쌍이 존재할 경우, 해당 쌍들을 모두 결과에 추가하고 각각의 포인터를 앞으로 이동시킨 뒤 다음 단계를 진행합니다. 결과 배열의 길이가 num에 도달하거나 더 이상 만들 수 있는 쌍이 없으면 탐색을 종료합니다.

구현 코드

이를 구현한 코드는 다음과 같습니다 —

const arr1 = [1, 1, 2];
const arr2 = [1, 2, 3];
const num = 2;
const smallestPairs = (arr1 = [], arr2 = [], num = 1) => {
    const temp = Array(arr1.length).fill(0);
    const res = [];
    let compute = () => {
        let flag = Infinity;
        for (let i = 0; i < arr1.length; i++) {
            if (temp[i] < arr2.length && flag > (arr1[i] + arr2[temp[i]])) {
                flag = arr1[i] + arr2[temp[i]];
            }
        }
        if (flag === Infinity || res.length >= num) {
            return;
        } else {
            for (let i = 0; i < arr1.length; i++) {
                if (temp[i] < arr2.length && flag == (arr1[i] + arr2[temp[i]])) {
                    res.push(Array.of(arr1[i], arr2[temp[i]]));
                    temp[i]++;
                }
            }
            compute();
        }
    }
    compute();
    return res.slice(0, num);
};
console.log(smallestPairs(arr1, arr2, num));

출력 결과

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

[ [ 1, 1 ], [ 1, 1 ] ]