지난 글에서는 배열의 참조를 건드릴 때 생기는 문제와 얕은 복사로 해결하는 방법을 살펴봤다. 반대로 참조값을 이용하면 해결하기 편한 문제도 있는데 함께 풀어보자.
구간 병합 (Merge Intervals)
구간들의 배열이 주어졌을 때, 겹치는 구간들을 전부 합쳐서 겹치지 않는 구간들의 배열을 반환해라.
Example 1
입력: [[1,3],[2,6],[8,10],[15,18]]
출력: [[1,6],[8,10],[15,18]]
[1,3]과 [2,6]이 겹치므로 [1,6]으로 합친다.
Example 2
입력: [[1,4],[4,5]]
출력: [[1,5]]
[1,4]와 [4,5]는 4에서 맞닿아 있으므로 [1,5]로 합친다.
Example 3
입력: [[4,7],[1,4]]
출력: [[1,7]]
[4,7]과 [1,4]는 4에서 맞닿아 있으므로 [1,7]로 합친다.
조건
- 구간
[start, end]에서 start와 end가 같은 값이면 겹치는 것으로 판단한다. - 입력 배열이 정렬되어 있다는 보장이 없다.
0 <= start <= end <= 10,000
Try 1
처음에는 이런 방식을 생각했다.
- 10000 크기의 큰 메모리 띠(배열)를 만들고, 0으로 초기화 해놓는다.
intervals를 돌면서 위에서 만든 배열에 1로 체크한 뒤 1이 시작되고 끊기는 지점을 계산해 정답 배열에 push한다.
테스트 케이스는 통과했지만, 입력이 [[1, 4], [5, 6]인 경우는 해결하기 어렵다. [[1, 4], [5, 6] 그대로가 정답이지만 [1, 6]으로 출력된다. 시작점을 판단하는 배열을 새로 만들어서 풀어봤지만, 입력이 정렬이 되지 않은 경우엔 풀기 어려웠다.
sort()의 시간복잡도
시작점을 판단하는 기준을 바꿔야 한다. 먼저 정렬을 하는 게 나은데 자바스크립트 sort()의 시간복잡도는 얼마일까?
입력 배열의 길이가 10,000 이다보니 최대 O(NlogN)에 풀어야 한다고 생각했다. 기본 정렬의 시간 복잡도는 대충 알고 있었지만 확실하지 않아 찾아보니 TimSort를 사용해 O(NlogN)을 보장한다고 한다. TimSort는 '배열에는 정렬이 되어있는 부분이 존재한다' 는 전제로 병합 정렬과 삽입 정렬을 활용해 시간복잡도를 최적화한다.
logN은 2를 몇 번 곱하면 N이 되냐는 뜻이다. N = 10,000 일 때, NlogN은 130,000이고 N = 1,000,000 이라도 20,000,000 이므로 sort()를 사용해도 된다.
풀이 전략
- start를 기준으로 각 Interval을 정렬한다.
- result에 담긴 마지막 Interval의 end와 현재 Interval의 start를 비교한다. 따라서 result에는 첫번재 Interval을 미리 넣어놔야 한다.
- 현재 start가 더 크다면, 새로운 배열로 만들어 result에 넣는다.
- 현재 start가 더 작다면, 마지막 Interval의 end와 현재 Interval의 end 값을 비교해 더 큰 값으로 업데이트한다.
function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const [start, end] = intervals[i];
const last = result[result.length - 1];
if (start > last[1]) {
result.push(intervals[i]);
} else {
last[1] = Math.max(last[1], end);
}
}
return result;
}
이렇게 result에 담긴 마지막 배열의 참조를 수정하면 편하게 풀 수 있다.