JavaScript로 여러 객체의 배열 값 중 최단 거리 조합 찾기

다음과 같이 배열들을 값으로 가지는 객체가 있다고 가정해 보겠습니다.

const obj = {
    obj1: [ 0, 10 ],
    obj2: [ 3, 9 ],
    obj3: [ 5, 12, 14 ]
};

이러한 배열 객체를 입력으로 받아 처리하는 JavaScript 함수를 작성해야 합니다. 주의할 점은 각 객체가 두 개 이상의 거리 지점(distance point)을 가지고 있지만, 다른 객체와 조합할 때는 각 객체에서 단 하나의 지점만 선택해야 한다는 것입니다.

문제 이해하기

위의 거리 지점들을 기준으로 세 객체를 조합할 수 있는 방법은 총 12가지입니다. 몇 가지 예를 살펴보겠습니다.

[0, 3, 5]로 조합하는 경우 → 거리는 5 − 0 = 5
[10, 9, 5]로 조합하는 경우 → 거리는 10 − 5 = 5
[0, 3, 12]로 조합하는 경우 → 거리는 12 − 0 = 12

우리가 구하고자 하는 것은 이중에서 가장 짧은 거리를 가지는 조합입니다. 이 예제에서는 [10, 9, 12]가 정답이며, 거리는 12 − 9 = 3입니다.

여기서 말하는 '최단 거리'란 조합된 그룹 안에서 가장 큰 요소와 가장 작은 요소의 차이를 의미합니다.

접근 방식

이 문제는 모든 조합을 일일이 확인하는 브루트 포스 방식보다 훨씬 효율적으로 풀 수 있습니다. 핵심 아이디어는 다음과 같습니다.

모든 숫자를 하나의 배열로 모은 뒤, 각 숫자가 어느 객체에 속했는지 표시합니다.
숫자 값을 기준으로 오름차순 정렬합니다.
정렬된 배열을 순회하면서 슬라이딩 윈도우 방식으로 세 객체의 지점이 모두 포함되는 구간을 추적합니다.
모든 객체가 포함된 시점마다 최댓값과 최솟값의 차이를 계산하여, 기존 결과보다 작으면 갱신합니다.

예제 코드

const obj = {
    obj1: [ 0, 10 ],
    obj2: [ 3, 9 ],
    obj3: [ 5, 12, 14 ]
};
const findNearest = (obj = {}) => {
    let parts = [undefined, undefined, undefined];
    let i;
    let res;
    const data = Object
    .values(obj)
    .map((a, i) => a.map(v => [v, i]))
    .reduce((a, b) => a.concat(b))
    .sort((a, b) => a[0] − b[0] || a[1] − b[1]);
    for (i = 0; i < data.length; i++) {
        parts[data[i][1]] = data[i][0];
        if (parts.some(v => v === undefined)) continue;
        if (!res || Math.max(...parts) − Math.min(...parts) <
        Math.max(...res) − Math.min(...res)) {
            res = parts.slice();
        };
    };
    return res;
};
console.log(findNearest(obj));

코드 설명

Object.values(obj)로 객체의 모든 배열을 가져온 후, map을 통해 각 숫자를 [값, 객체 인덱스] 형태의 쌍으로 변환합니다.
reduce와 concat으로 모든 쌍을 하나의 배열로 합친 뒤, 값 기준으로 정렬합니다.
정렬된 데이터를 순회하면서 parts 배열에 각 객체의 지점을 기록하고, 세 객체가 모두 채워졌는지 검사합니다.
모두 채워진 시점에 최댓값과 최솟값의 차이를 계산해, 지금까지의 최소 거리보다 작으면 결과를 저장합니다.

실행 결과

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

[ 10, 9, 12 ]

이처럼 정렬과 슬라이딩 윈도우 기법을 활용하면 모든 조합을 탐색하지 않고도 O(n log n)의 시간 복잡도로 최단 거리 조합을 효율적으로 찾을 수 있습니다.