10/24 (화) 인터벌 끼워넣기 TIL

공부한 것

LeetCode #57. Insert Interval

방법 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

공부한 것

티스토리툴바