Insert Interval

문제

겹치지 않는 구간들이 시작점 기준으로 오름차순 정렬된 배열 intervals와 새로운 구간 newInterval이 주어집니다. newInterval을 intervals에 올바른 위치에 삽입하고, 겹치는 구간이 있다면 모두 병합하여 새로운 구간 배열을 반환하는 프로그램을 작성하는 문제입니다.

제한사항 (Constraints)

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^5
• intervals는 starti를 기준으로 오름차순 정렬되어 있습니다.
• newInterval.length == 2
• 0 <= start <= end <= 10^5

링크: https://leetcode.com/problems/insert-interval

풀이: 3단계 while문을 활용한 완벽한 구간 분리 및 병합

복잡한 if문 분기 대신, 탐색 과정을 시간 순서에 따라 정확히 3단계로 나누어 처리하는 방식입니다. 인덱스 idx 하나를 사용하여 배열을 단 한 번만 순회(O(N))하므로 매우 직관적이고 버그 발생 확률이 낮습니다.

1. 앞부분 (겹치지 않는 구간): intervals의 끝점(intervals[idx][1])이 newInterval의 시작점(newInterval[0])보다 엄격히 작은 구간들은 전혀 겹치지 않으므로 그대로 정답 리스트에 추가합니다.
2. 중간부분 (겹치는 구간 병합): intervals의 시작점(intervals[idx][0])이 newInterval의 끝점(newInterval[1])보다 작거나 같은 동안에는 계속해서 겹침이 발생합니다. 이때 newInterval의 시작점은 Math.min으로 가장 작게, 끝점은 Math.max로 가장 크게 지속적으로 갱신하여 하나의 거대한 구간으로 병합합니다. 병합이 끝나면 최종 완성된 newInterval을 리스트에 추가합니다.
3. 뒷부분 (남은 구간): 병합이 끝난 이후에 남은 구간들은 newInterval보다 완전히 뒤에 있는 구간들이므로 그대로 리스트에 마저 추가합니다.

코드

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list = new ArrayList<>();
        int idx = 0;
        int n = intervals.length;

        // 1. newInterval보다 완전히 앞에 있는 구간들을 모두 추가
        while (idx < n && intervals[idx][1] < newInterval[0]) {
            list.add(intervals[idx]);
            idx++;
        }

        // 2. newInterval과 겹치는 구간들을 모두 하나로 병합
        while (idx < n && intervals[idx][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[idx][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[idx][1]);
            idx++;
        }
        // 병합이 완료된 최종 newInterval 추가
        list.add(newInterval);

        // 3. newInterval보다 완전히 뒤에 있는 남은 구간들을 모두 추가
        while (idx < n) {
            list.add(intervals[idx]);
            idx++;
        }

        // List를 2차원 int 배열로 변환하여 반환
        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        
        return ans;
    }
}

알고리즘 분류

배열 (Array), 구현 (Implementation)