📌 문제 설명

Merge Intervals 문제 보기

📌 문제 접근

처음 문제 접근

그냥 배열을 타임 라인처럼 펼쳐놓고 그 위에 기록하면 되지 않을까? 해서 시도해봤다.

/**

 * @param {number[][]} intervals

 * @return {number[][]}

 */

const merge = (intervals) => {
  const q = Array.from({ length: 10001 }, () => false);

  for (const [start, end] of intervals) {
    for (let i = start; i <= end; i++) q[i] = true;
  }

  const answer = [];

  let idx = 0;

  for (let i = 0; i < q.length; i++) {
    if (q[i] && !idx) idx = i;
    else if (!q[i] && idx) {
      answer.push([idx, i - 1]);

      idx = 0;
    }
  }

  return answer;
};

첫 번째 시도 문제점

이 방법에서 intervals = [[1, 4], [5, 6]] 이 부분에서 문제가 생겼다. 바로 하나로 합쳐버리기 때문이다. 따라서 새로운 방법을 시도했다.

두 번째 문제 접근

정렬 후, 현재 구간의 시작점이 이전 구간의 끝점보다 작거나 같으면 합치고, 그렇지 않으면 새로운 구간으로 추가한다. 대신 sort를 사용해야 해야하는 문제가 있지만, 이렇게 하면 메모리 사용량을 줄일 수 있다. 그리고 무엇보다 위의 문제를 해결할 수 있다.

📌 내가 작성한 코드

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
const merge = (intervals) => {
  intervals.sort((a, b) => a[0] - b[0]);
  const answer = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const lastMerged = answer.at(-1);
    if (lastMerged[1] >= current[0]) {
      lastMerged[1] = Math.max(lastMerged[1], current[1]);
    } else {
      answer.push(current);
    }
  }

  return answer;
};

📌 시간 복잡도

O(N log N) - 정렬에 지배적이므로 (N: 구간 개수)

📌 참고 링크

• Array.sort() - MDN

• Array.at() - MDN