공부한 것
- LeetCode #57. Insert IntervalInsert Interval - LeetCodeCan 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/
- 방법 1: 생각의 흐름대로 로직을 구성하여 답을 내놓음 ⇒ intervals 목록을 필요할 때마다 반복해서 순회하기 때문에 테스트에 통과는 하지만 시간 효율이 좋지 못함. 리팩토링 필요.
방법 1 풀이 코드:
/* 대략적인 아이디어: ^ 1. 새로 들어오는 인터벌의 시작과 끝을 재정립하기 1) 새 인터벌의 시점: 만약 기존의 인터벌의 간격 이내라면(시작과 끝 포함), 그 인터벌의 시작지점으로 새 인터벌의 시작을 옮긴다. 새 인터벌의 시점이 어떤 인터벌에도 속하지 않는다면 그대로 둔다. 2) 새 인터벌의 종점: 만약 어떤 인터벌의 중간 지점이거나 시작지점과 만난다면 그 인터벌의 끝을 새로운 종점으로 설정한다. 만약 어떤 인터벌의 끝과 만나거나 어떤 인터벌과도 접하지 않는다면, 그대로 둔다. ^ 2. 수정한 '새 인터벌'의 시점과 종점을 기존 목록과 비교하기 1) 기존 목록의 종점이 새 것의 종점보다 작은 동안 루프를 돈다: 시점이 새 것의 시점과 같거나 큰 경우 그 인터벌을 삭제 대상으로 포함. ^ 3. 찾은 '삭제 대상' 지우기 및 수정한 '새 인터벌' 삽입 어떻게 하면 더 효과적으로 처리할 수 있을까 */ function insert2(intervals: number[][], newInterval: number[]): number[][] { if (intervals.length === 0) return [newInterval]; // 1-1. 새 인터벌의 시점 수정하기 let [newStart, newEnd] = newInterval; let i = 0; for (; i < intervals.length; i++) { let [start, end] = intervals[i]; if (newStart >= start && newStart <= end) { // 기존 인터벌의 간격 이내일 때, 시점 수정 newStart = start; break; } } // 1-2. 새 인터벌의 종점 수정하기 for (; i < intervals.length; i++) { // 새 인터벌이 '시작'한 부분부터 검사 시작 let [start, end] = intervals[i]; if (newEnd >= start && newEnd <= end) { // 기존 인터벌의 시점과 같거나 간격 내일 때(종점 미포함)(종점 포함해도 상관없음) newEnd = end; break; } } // 1-3. 새 인터벌의 시작점은 기존 인터벌에 포함되지 않지만 종점은 포함되어 있을 때: 새 인터벌의 시점은 그대로 두고 종점만 그 지점으로 옮긴다 for (let i = 0; i < intervals.length; i++) { let [start, end] = intervals[i]; if (newEnd >= start && newEnd <= end) { newEnd = end; break; } } // 2. 수정한 '새 인터벌'의 시점과 종점을 기존 목록과 비교하기 let j = 0; let [start, end] = intervals[j]; let hasReplaced = false; // 기존 인터벌의 종점이 새것과 같은 것을 발견할 때까지 while (end <= newEnd && j < intervals.length) { if (start >= newStart) { // 처음 '삭제 대상'을 발견한 자리에 수정한 '새 인터벌'을 덮어씌운다. if (!hasReplaced) { intervals[j] = [newStart, newEnd]; hasReplaced = true; } // 이후 발견하는 '삭제 대상'들은 그냥 삭제한다. else delete intervals[j]; // 이후 .filter(x=>true)로 반환 } [start, end] = intervals[++j] ?? [null, null]; } intervals = intervals.filter(x => true) // 3. '대체할' 기존 인터벌을 찾지 못했어도 넣어야 한다. if (!hasReplaced) { for (let j = 0; j < intervals.length; j++) { if (newStart < intervals[j][0]) { intervals = [...intervals.slice(0, j), [newStart, newEnd], ...intervals.slice(j)]; hasReplaced = true; break; } } } if (!hasReplaced) intervals.push([newStart, newEnd]); return intervals; };
Uploaded by N2T