JavaScript로 두 간격 배열의 교차 구간 효율적으로 구하기

문제 개요

이번 글에서는 JavaScript로 서로 겹치지 않고(쌍별로 분리되어 있으며) 정렬된 순서로 주어진 두 간격 배열 arr1과 arr2를 입력받아, 두 배열의 교차 구간을 반환하는 함수를 작성해 보겠습니다.

먼저 닫힌 구간(closed interval) [a, b](단, a <= b)은 a <= x <= b를 만족하는 실수 x의 집합을 의미합니다.

두 닫힌 구간의 교집합은 공집합이거나 하나의 닫힌 구간으로 표현됩니다. 예를 들어, [1, 3]과 [2, 4]의 교집합은 [2, 3]입니다. 우리가 만들 함수는 이처럼 두 간격 배열 전체에 대한 교집합 결과를 반환해야 합니다.

입력 예시

함수에 다음과 같은 입력이 주어졌다고 가정해 봅시다.

const arr1 = [[0,2],[5,10],[13,23],[24,25]];
const arr2 = [[1,5],[8,12],[15,24],[25,26]];

그렇다면 기대하는 출력 결과는 다음과 같습니다.

const output = [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]];

풀이 코드

이 문제는 투 포인터(Two Pointer) 기법을 활용하면 O(n + m)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 두 배열이 이미 정렬되어 있으므로, 각 배열을 가리키는 포인터 i와 j를 사용해 한 번의 순회만으로 모든 교차 구간을 찾을 수 있습니다.

핵심 아이디어는 다음과 같습니다.

두 구간 [a, b]와 [c, d]의 교집합 시작점은 Math.max(a, c), 끝점은 Math.min(b, d)가 됩니다.
시작점이 끝점보다 작거나 같으면(lo <= hi) 유효한 교차 구간이므로 결과에 추가합니다.
교집합 계산 후에는 끝점이 더 작은 쪽의 포인터를 앞으로 이동시킵니다. 끝점이 작은 구간은 더 이상 다른 구간과 겹칠 가능성이 없기 때문입니다.

const arr1 = [[0,2],[5,10],[13,23],[24,25]];
const arr2 = [[1,5],[8,12],[15,24],[25,26]];

const findIntersection = function (A, B) {
    const res = []
    let i = 0
    let j = 0
    while (i < A.length && j < B.length) {
        const [a, b] = A[i]
        const [c, d] = B[j]
        const lo = Math.max(a, c)
        const hi = Math.min(b, d)
        if (lo <= hi) {
            res.push([lo, hi])
        }
        if (b < d) {
            i++
        } else {
            j++
        }
    }
    return res
};

console.log(findIntersection(arr1, arr2));

실행 결과

위 코드를 콘솔에서 실행하면 다음과 같은 결과가 출력됩니다.

[
    [ 1, 2 ],
    [ 5, 5 ],
    [ 8, 10 ],
    [ 15, 23 ],
    [ 24, 24 ],
    [ 25, 25 ] 
]

[5, 5], [24, 24], [25, 25]처럼 시작점과 끝점이 같은 단일 값 구간도 유효한 교차 구간으로 처리되는 점에 주목하세요. 이 알고리즘은 두 배열을 한 번씩만 순회하므로, 시간 복잡도는 O(n + m), 공간 복잡도는 결과 크기를 제외하면 O(1)로 매우 효율적입니다.