깊은바다거북
개발 공부 기록
깊은바다거북
전체 방문자
오늘
어제
  • 분류 전체보기 (219)
    • JAVA (9)
    • JavaScript (15)
    • 스파르타코딩클럽 (11)
      • [내일배움단] 웹개발 종합반 개발일지 (5)
      • [내일배움캠프] 프로젝트와 트러블 슈팅 (6)
    • SQL | NoSQL (4)
    • CS 등등 (0)
    • TIL | WIL (173)
    • 기타 에러 해결 (3)
    • 내 살 길 궁리 (4)

인기 글

최근 글

최근 댓글

태그

  • 혼자 공부하는 자바스크립트
  • 팀 프로젝트
  • 자바스크립트 기초 문법
  • TIT (Today I Troubleshot)
  • Leetcode
  • BST(이진 탐색 트리)
  • 자잘한 에러 해결
  • leetcode-cli
  • 01. 미니 프로젝트
  • Binary Tree(이진 트리)
  • BFS(너비우선탐색)
  • 트러블 슈팅 Troubleshooting
  • DFS(깊이우선탐색)
  • 재귀 함수
  • Linked List
  • 자료 구조
  • 시간 복잡도
  • tree
  • 점화식(Recurrence Relation)
  • Til
  • POST / GET 요청
  • 최대 힙(Max Heap)
  • Backtracking(백트래킹)
  • 코딩테스트 연습문제
  • Trie
  • Preorder Traversal(전위 순회)
  • 프로그래머스
  • TypeScript
  • 최소 힙(Min Heap)
  • Inorder Traversal(중위 순회)
hELLO · Designed By 정상우.
깊은바다거북

개발 공부 기록

TIL | WIL

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

2023. 10. 25. 22:04

공부한 것

  • 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

    'TIL | WIL' 카테고리의 다른 글
    • 10/27 (금) 인터벌이 안 겹치도록 삭제해야 하는 최소 인터벌 개수 TIL
    • 10/26 (목) 겹치는 인터벌 합치기 TIL
    • 10/24 (화) 인터벌 끼워넣기 TIL
    • 10/23 (월) (완료)스트림에서 중위값 찾기 TIL
    깊은바다거북
    깊은바다거북

    티스토리툴바