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

공부한 것

LeetCode #57. Insert Interval

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

공부한 것

티스토리툴바