JavaScript에서 정렬된 간격 배열에 새 간격 삽입하는 방법

이 문제에서는 간격(interval)을 두 개의 숫자로 이루어진 배열로 정의하며, 항상 첫 번째 숫자가 두 번째 숫자보다 작아야 합니다.

예를 들면 다음과 같습니다.

[4, 6], [2, 3], [6, 8], [2, 7], [1, 8]은 모두 유효한 간격의 예입니다.

문제 상황

시작 시간(각 간격의 첫 번째 요소)을 기준으로 정렬된 간격 배열이 있다고 가정해 보겠습니다. 배열 내 간격들은 서로 겹치지 않습니다(non-overlapping). 즉, 임의의 인접한 두 간격 [m, n]과 [x, y]에 대해 다음 조건이 항상 성립합니다.

m < n < x < y

따라서 이러한 간격 배열의 대표적인 예는 다음과 같습니다.

const arr = [[2, 4], [5, 7], [9, 10], [13, 17]];

해결해야 할 작업

정렬된 간격 배열을 첫 번째 인수로, 하나의 새 간격을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 새 간격을 배열 내 올바른 위치에 삽입하고, 배열의 비겹침 속성을 유지해야 합니다. 필요하다면 두 개 이상의 간격을 병합하여 배열의 간격들이 서로 겹치지 않도록 처리할 수 있습니다.

예를 들어, 위의 간격 배열에 [6, 13] 간격을 삽입해야 한다면 출력 결과는 다음과 같아야 합니다.

const output = [[2, 4], [5, 17]];

예제 코드

다음은 위 문제를 해결하는 전체 코드입니다.

const arr = [[2, 4], [5, 7], [9, 10], [13, 17]];
const interval = [6, 13];
const insertWithin = (arr = [], interval = []) => {
    const res = [];
    let ind = 0;
    // 1단계: 새 간격보다 앞에 있는 간격들을 그대로 추가
    while (arr[ind] && arr[ind][1] < interval[0]) {
        res.push(arr[ind]);
        ++ind;
    }
    let start = interval[0];
    let end = interval[1];
    // 2단계: 새 간격과 겹치는 간격들을 하나로 병합
    while (arr[ind] && arr[ind][0] <= interval[1]) {
        start = Math.min(start, arr[ind][0]);
        end = Math.max(end, arr[ind][1]);
        ++ind;
    }
    res.push([start, end]);
    // 3단계: 나머지 간격들을 그대로 추가
    while (arr[ind]) {
        res.push(arr[ind]);
        ++ind;
    }
    return res;
};
console.log(insertWithin(arr, interval));

코드 동작 원리

이 알고리즘은 크게 세 단계로 동작합니다.

1단계: 끝점이 새 간격의 시작점보다 작은, 즉 새 간격보다 완전히 앞에 있는 기존 간격들은 결과 배열에 그대로 추가합니다.

2단계: 새 간격과 겹치는 모든 간격을 찾아 하나로 병합합니다. 병합된 간격의 시작점은 겹치는 간격들과 새 간격의 시작점 중 최솟값으로, 끝점은 그중 최댓값으로 결정됩니다.

3단계: 아직 처리하지 않은 나머지 간격들을 결과 배열 뒤에 그대로 추가합니다.

이 알고리즘은 입력 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 여기서 n은 입력 배열의 길이입니다. 추가 배열을 사용하지만 기존 순서를 유지하면서 안전하게 병합할 수 있다는 장점이 있습니다.

출력 결과

위 코드를 실행했을 때 콘솔 출력은 다음과 같습니다.

[[2, 4], [5, 17]]