10/25 (수) (완료)인터벌 끼워넣기 TIL

공부한 것

• LeetCode #57. Insert Interval

  Insert Interval - LeetCode

  Can you solve this real interview question? Insert Interval - You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.   Example 1: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].   Constraints: * 0 <= intervals.length <= 104 * intervals[i].length == 2 * 0 <= starti <= endi <= 105 * intervals is sorted by starti in ascending order. * newInterval.length == 2 * 0 <= start <= end <= 105

  https://leetcode.com/problems/insert-interval/description/

  

  • 방법 2(통과): 반환할 새 배열을 만들고, 통합된 새 시작점과 새 끝점을 구하여 이 사이의 점 들을 제외한 나머지 점들을 옮겨담아 반환하는 방식. 방법 1보다 확실히 빨라졌다. 다만 메모리 사용이 조금 많음.
  • 방법3(통과): 시간, 공간, 가독성 모두 좋은데 가독성이 가장 발군인 풀이법. 방법1이나 방법2와 아이디어가 같은데 math.Max()와 math.Min()을 활용해 새 인터벌의 시점과 끝점을 점점 양옆으로 확장해나가는 방식을 사용한 것이 눈에 띈다.
  • 방법 2 풀이 코드:

    /* 대략적인 아이디어: 
    	 새롭게 배열을 만든다. 통합된 시작점 전의 점까지를 넣고, 통합된 시작점을 넣고, 이후 점들은 건너뜀. 이후 통합된 끝점와 그 이후의 점들을 넣고서 두 짝씩 묶는다. 틀림없이 두 짝이 맞게 되며, 반환한다. 
    */ 
    function insert2(intervals: number[][], newInterval: number[]): number[][] {
    	// 0. 
    	if (!intervals.length) return [newInterval];
    
    	// 편하게 하기 위해 intervals를 평면화시킴([[1,3],[6,9]] => [1,3,6,9])
    	const dots = intervals.flatMap((interval) => interval);
    
    	const result = [];
    	const [newStart, newEnd] = newInterval;
    	let newStartFound = false, newEndFound = false;
    	let i = 0; 
    	
    	// newStart이 나타나는 지점 찾기
    	for (; i < dots.length; i++) {
    		if (dots[i] >= newStart) {
    			if (dots[i] !== newStart && i % 2 === 0) { // 간격 '외'임
    				result.push(newStart);
    			} else { // 간격 '내'임. 
    				if (dots[i] === newStart && i % 2 === 0) { // 지금 i를 '시작점'으로 삼고 이후 나타나는 점들을 건너뛴다. 
    					// = i번째 점은 넣어줌.
    					result.push(dots[i]);
    				} else { // i 이전 점을 '시작점'으로 삼는다
    					// = i부터 건너뜀	
    				}
    			}
    			newStartFound = true;
    			break;
    		}
    		// newStart이 나타나기 전까지는 점들을 다 넣어준다. 
    		else {
    			result.push(dots[i]);
    		}
    	}
    
    	// newEnd가 나타나는 지점 찾기
    	for (; i < dots.length; i++) {
    		if (dots[i] >= newEnd) {
    			if (dots[i] !== newEnd && i % 2 === 0) { // 간격 '외'임
    				result.push(newEnd);
    			} else {
    				if (dots[i] === newEnd && i % 2 === 0) { // i 다음 점을 '끝점'으로 삼는다 = i까지 건너뛴다
    					i++;
    				} else { // i를 '끝점'으로 삼는다 = 점 i는 추가한다.
    					// result.push(dots[i]);
    				}
    			}
    			newEndFound = true;
    			break;
    			// FIXME: break하기 전에 점이 겹치지 않았으면 i--를 해줘야 함.
    			// 		=> i++를 넣어주고, result.push(dots[i])를 주석 처리해준 후, 루프 바깥에서 result.push(...dots.slice(i+1))을 slice(i)로 바꿔줌으로써 달성함. 
    		}
    		// newEnd가 나타나기 전까지는 점들을 다 건너뛴다.
    	}
    
    	// newEnd 이후 점들을 다 넣어주기
    	result.push(...dots.slice(i));
    	
    	// dots의 끝점에 도달할때까지 newStart이나 newEnd를 찾을 수 없는 경우
    	if (!newStartFound)
    		// 제일 마지막에 newIntervals의 두 점을 넣어준다
    		result.push(newStart, newEnd);
    	else if (!newEndFound)
    		// 끝점 newEnd만 추가해준다. 
    		result.push(newEnd);
    	
    	// 최종 점들을 두 짝씩 묶어서 반환하기
    	const newIntervals = []
    	for (let i = 0; i < result.length; i += 2) {
    		newIntervals.push([result[i], result[i + 1]]);
    	}
    	return newIntervals;
    }

  • 방법 3 풀이 코드:

    // 전과 같은 아이디어이나 가독성이 좋은: 
    function insert4(intervals: number[][], newInterval: number[]): number[][] {
    	const newIntervals = [];
    	const m = intervals.length;
    	let i = 0;
    
    	while (i < m && intervals[i][1] < newInterval[0]) {
    		newIntervals.push(intervals[i]);
    		i++;
    	}
    	
    	while (i < m && intervals[i][0] <= newInterval[1]) {
    		newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
    		newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
    		i++;
    	}
    
    	newIntervals.push(newInterval);
    
    	while (i < m) {
    		newIntervals.push(intervals[i]);
    		i++;
    	}
    
    	return newIntervals;
    }

  결과:

  

  풀이 1과 비교:

  

Uploaded by N2T