[Leetcode] 56. Merge Intervals - JS

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

 

 

1. 문제 분석

문제분석
--------------------
- intervals 배열이 주어진다.
- intervals[i] = [start, end]
- 겹치는 간격을 모두 병합하고 겹치지 않는 간격의 배열을 반환하라

제한조건
--------------------
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= start <= end <= 10^4

 

2. 접근 방법

접근방법
--------------------
merged 배열 선언 = []
prev = intervals[0]

intervals 1번째부터 순회한다.
현재 간격의 start <= 이전 간격의 end 면...

1 ~ 3
  2 ~ 6

위 경우 [1, 6]으로 병합한다.

prev = [이전간격 start, Math.max(이전 간격의 end, 현재간격 end)]으로 이전 간격의 end 값을 수정한다.
결과배열에 바로 추가 하지 않고 prev 배열을 수정하는 이유는
이후에 병합할 수 있는 모든 간격들을 병합해야하기 때문이다.

병합 조건에 맞지 않을 때, 그동안 누적된 이전 간격 배열(prev)을 merged 배열에 추가하고
이전 간격을 현재 간격으로 갱신한다.

반복문 내에서는 merged 배열에 prev 값만 추가해준다.
반복문이 종료되어 마지막 간격이 조건에 따라 prev와 병합되거나 
prev로 갱신된 마지막 간격은 아직 merged에 추가되지 않았으므로
반복문이 종료되면 merged 배열에 추가해줘야한다.

 

 

3. 코드

var merge = function(intervals) {
    intervals.sort((a,b) => a[0] - b[0]);
    const merged = [];

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

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

 

 

4. 복잡도 분석

- 시간복잡도: O(nlogn)

- 공간복잡도: O(n)

 

병합한 값을 누적하여 이후에 나올 요소까지 같이 병합하는 로직을 머릿속으로 코딩하기가 아직은 낯설다.

intervals 배열이 start < end 조건을 만족하므로 start를 오름차순으로 정렬하면 반복문 순회시 비교가 편할 것 같은 생각은 했다.

그리고 1번째 부터 순회하여 이전 값과 비교하는 방법도 생각했다.

 

하지만 이전 값과 비교하여 병합 조건을 만족할 때, 병합된 값에 대한 처리 방법을 몰랐다.

prev 라는 이전 간격 변수에 병합된 값을 저장하여 이후에 병합 조건에 만족하지 않을 때,

merged 배열에 prev를 추가한 뒤 prev를 현재 간격으로 갱신하는 방법으로 병합된 간격을 유지할 수 있었다.

 

마지막으로 반복문 내에서는 병합된 값(prev)만 merged 배열에 추가해주고 있기 때문에

반복문이 종료되었을 때 마지막 간격이 적용된 값은 추가되지 않았다.

 

결과적으로 반복문이 종료되었을 때, prev 값을 merged에 추가해줘야지만

마지막 반복문에서 prev[1]이 갱신되거나 prev = interval로 갱신된 값을 추가해줄 수 있다.