공부한 것
- LeetCode #56. Merge Interval
- 어제는 이미 정렬된 인터벌들에 새 인터벌을 하나 끼우는 방식으로, 전체를 한 번만 순회하기 때문에 시간 복잡도는
이면 되었다.
- 오늘은 정렬되지 않은 전체 인터벌을 겹치는 것끼리 병합하는 문제로, 먼저 정렬 후 전체를 한 번 순회해야 하기 때문에 시간 복잡도가
이다.
방법 1: 반환할 인터벌들을 새 배열 result에 넣는 방법
// Time Complexity: O(n log n) // Space Complexity: O(n) function merge1(intervals: number[][]): number[][] { if (intervals.length === 1) return intervals; // 1. start 기준으로 오름차순 정렬하기: O(N logN) intervals.sort((a, b) => a[0] - b[0]); const result = [intervals[0]]; // 2. 어느 두 연이은 인터벌 중 앞의 end가 뒤의 start보다 크거나 같으면 병합한다: O(N) for (let i = 1; i < intervals.length; i++) { const pre = result[result.length - 1]; const post = intervals[i]; if (pre[1] >= post[0]) { // 병합하기 pre[1] = Math.max(pre[1], post[1]); } else { // 새 인터벌 등장. result에 넣기 result.push(post); } } return result; };
방법 2: result 배열을 사용하지 않는 방법
// 새 result 배열 없이 해보기: // Time Complexity: O(n log n) // Space Complexity: O(log n) (in-place sorting을 하므로) function merge(intervals: number[][]): number[][] { if (intervals.length === 1) return intervals; // 1. start 기준으로 오름차순 정렬하기: O(N logN) intervals.sort((a, b) => a[0] - b[0]); // 2. 어느 두 연이은 인터벌 중 앞의 end가 뒤의 start보다 크거나 같으면 병합한다: O(N) let pre = intervals[0]; for (let i = 1; i < intervals.length; i++) { const post = intervals[i]; if (pre[1] >= post[0]) { // 병합하기 pre[1] = Math.max(pre[1], post[1]); delete intervals[i]; // delete post;는 안 됨 주의 } else { // 새 인터벌 등장. pre를 새 인터벌로 옮긴다. pre = post; } } return intervals.filter(x => true); };
결과: 방법 1과 방법 2에서 유의미한 메모리 차이는 발생하지 않음.
- 어제는 이미 정렬된 인터벌들에 새 인터벌을 하나 끼우는 방식으로, 전체를 한 번만 순회하기 때문에 시간 복잡도는
Uploaded by N2T