10/26 (목) 겹치는 인터벌 합치기 TIL

공부한 것

• LeetCode #56. Merge Interval

  LeetCode - The World's Leading Online Programming Learning Platform

  Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

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

  

  • 어제는 이미 정렬된 인터벌들에 새 인터벌을 하나 끼우는 방식으로, 전체를 한 번만 순회하기 때문에 시간 복잡도는 $O(n)$이면 되었다.
  • 오늘은 정렬되지 않은 전체 인터벌을 겹치는 것끼리 병합하는 문제로, 먼저 정렬 후 전체를 한 번 순회해야 하기 때문에 시간 복잡도가 $O(n log n)$이다.
  • 방법 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