[Leetcode] 57. Insert Interval - JS

https://leetcode.com/problems/insert-interval/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- intervals는 중첩되지 않는 간격으로 구성된 배열이다.
- intervals[i]는 i번째 간격 [start, end]의 시작과 끝을 의미
- newInterval도 [start, end]인데, 이를 intervals에 추가하라.
- 만약 겹치는 구간이 있다면 병합하여 삽입 후 간견을 반환하라.
- 새로운 배열을 만들어서 반환해도 된다.

제한조건
--------------------
- 0 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= start <= end <= 10^5
- intervals는 start를 기준으로 오름차순 정렬됨
- newInterval.length == 2
- 0 <= start <= end <= 10^5

 

2. 접근 방법

접근방법
--------------------
merged 배열 초기화
newIntervals를 intervals에 추가한 뒤 start를 기준으로 오름차순 정렬
prev = intervals[0] 초기화

intervals를 1번째부터 순회
    - 현재 간격의 start <= prev의 end 만족하면 
        - prev의 end 최댓값 갱신 Math.max(prev의 end, 현재 간격의 end)
    - 그렇지 않으면 prev를 merged에 추가한 뒤 prev = 현재 간격으로 갱신

순회가 끝나면 마지막 상태 값인 prev 추가

 

 

3. 코드

var insert = function(intervals, newInterval) {
    const merged = [];
    intervals.push(newInterval);
    intervals.sort((a,b) => a[0] - b[0])
    let prev = intervals[0];

    for (let i = 1; i < intervals.length; i++) {
        const interval = intervals[i];

        if (interval[0] <= prev[1]) {
            prev[1] = Math.max(prev[1], interval[1])
        } else {
            merged.push(prev);
            prev = interval
        }
    }
    merged.push(prev);
    return merged;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

[Leetcode] 56. Merge Intervals - JS 문제에서 새롭게 추가된 간격을 병합하는 것만 추가된 문제여서

이전 문제와 비슷한 방법으로 풀어봤다.

하지만 newInterval을 interval에 추가하지 않고 푸는 방법도 있을 것 같아서 GPT를 통해 공부했다.

 

5. 또 다른 풀이 방법

var insert = function(intervals, newInterval) {
    const merged = [];
    let i = 0;
    const n = intervals.length;

    // 1. newInterval의 시작보다 작은 interval들을 그대로 추가
    while (i < n && intervals[i][1] < newInterval[0]) {
        merged.push(intervals[i]);
        i++;
    }

    // 2. newInterval과 겹치는 부분 병합
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    merged.push(newInterval); // 병합된 newInterval 추가

    // 3. 남은 interval들을 그대로 추가
    while (i < n) {
        merged.push(intervals[i]);
        i++;
    }

    return merged;
};

 

intervals는 start를 기준으로 오름차순 되어있고

현재 간격의 end < newInterval의 start 를 만족하면 겹치지 않는 구간이므로 merged에 추가한다.

 

다음 조건은 앞서 겹치지 않는 구간을 걸러줬으므로 겹치는 구간에 대한 처리를 해준다.

내가 푼 방법에선 prev라는 변수에 병합된 값들을 누적했다면

위 풀이에선 newInterval를 그대로 사용하여 병합된 값을 누적한다.

겹치는 부분으로 갱신해줄 때는 start는 비교하는 간격 중 더 작은 값을, end는 더 큰 값을 해준다.

 

마지막으로 겹치는 구간 처리도 끝나면 index가 intervals 길이 끝까지 남은 간격들을 merged에 추가한다.

 

이전 풀이방법과 차이점은 누적 병합 배열의 start 부분도 변경해주는 점이다.

start도 변경해주는 이유는 prev를 기준으로 병합하는 것이 아닌 newInterval을 기준으로 병합하기 때문이다.

 

예를들어, 현재 간격 = [3,5], newInterval = [4,8] 이면 [3,8]로 병합되어야 맞다.

때문에 newInterval 기준으로 start도 더 작은 값으로 변경해주는 것이 옳다.