[LeetCode] Merge Intervals (javascript)

주어진 2차배열 내의 요소들끼리 겹치는 것을 합쳐주는 문제다.

 

예를들어

[[1, 3], [2, 4], [5, 8]] 이 있다고 하면

이렇게 [[1, 4], [5, 8]]로 겹치는 요소는 합쳐주는 것이다.

 

여기서 각 요소의 첫 번째 요소([1, 4]의 1)를 head, 두 번째 요소([1, 4]의 4)를 tail이라고 부르겠다.

 

그래서 배열을 차례대로 돌면서, 현재 요소와 다음 요소가 겹치는 부분이 있으면 합치는 방식으로 풀었다.

 

어렵지 않게 풀리는듯 했으나 간과했던 포인트가 있었는데,

1. 주어진 배열들은 소팅되어 있지 않다. 즉, 차례대로 합치다간 나중에 제외되는 요소가 나타난다.

ex. [[1, 3], [2, 4], [5, 8], [2, 3]] => [[1, 4], [5, 8]]이 되어야 하나 [[1, 4], [5, 8], [2, 3]]이 된다.

=> 그래서 코드 초반에 각 요소의 head를 기준으로 sort하고 시작했다.

2. 반드시 앞 요소의 tail과 뒷 요소의 head가 교차하는 방식이 아니다. 아예 포함되는 형태일 수 있다.

ex. [[1, 5], [2, 3]]

=> 그러므로 배열을 합칠 때에는 head 중 작은 것과 tail중 큰 것으로 구성해 합쳐야한다.

 

위 포인트만 놓치지 않으면 구현 자체는 어렵지 않았다.

다만 테스트케이스에서 발견한 것이라, 통과하지 못한 테스트케이스가 비공개인 코딩테스트 등에서는 내가 발견할 수 있었을지 모르겠다. 많은 연습만이 답이겠지.. 

 

 

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 *
 * 정리
 *
 * [[prevHead, prevTail], [nextHead, nextTail], ...]
 * 1. prevHead 오름차순으로 정렬된 상태여야 한다.
 * 2. prevTail이 nextHead보다 크거나 같고, prevHead보다 nextTail이 크거나 같아야 겹친다.
 * 3. 겹치는 것을 찾았다면, 두 배열을 merge(splice)해준다.
 *   - 이 때, merge된 배열은 두 Head중 더 작은 것과 두 Tail중 더 큰 것으로 이루어진다.
 *   - [smaller Head, bigger Tail]
 * 4. 배열이 splice되며 index가 줄어들었으므로, merge될때마다 i-- 해준다.
 */
var merge = function (intervals) {
    const result = intervals.sort((a, b) => a[0] - b[0]);
    for (let i = 0; i < result.length - 1; i++) {
        if (!result[i + 1]) return;
        const [prevHead, prevTail, nextHead, nextTail] = [
            result[i][0],
            result[i][1],
            result[i + 1][0],
            result[i + 1][1],
        ];
        if (prevTail >= nextHead && prevHead <= nextTail) {
            result.splice(i, 2, [
                prevHead > nextHead ? nextHead : prevHead,
                prevTail < nextTail ? nextTail : prevTail,
            ]);
            i--;
        }
    }
    return result;
};

 

https://leetcode.com/problems/merge-intervals/