(Leetcode) 57 - Insert Interval 풀이
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/insert-interval/
57번 문제는 interval와 관련된 문제이다.
문제는 크게 어렵지 않게 해결되었다.
내가 작성한 풀이
from typing import List
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
startIndex = -1
endIndex = len(intervals)
if endIndex == 0:
return [newInterval]
elif intervals[0][0] > newInterval[1]:
return [newInterval] + intervals
elif intervals[len(intervals) - 1][1] < newInterval[0]:
return intervals + [newInterval]
for i, range in enumerate(intervals):
if startIndex == -1 and range[1] >= newInterval[0]:
startIndex = i
if range[0] <= newInterval[1]:
endIndex = i
newNode: List[int] = [intervals[startIndex][0] if intervals[startIndex][0] < newInterval[0] else newInterval[0],
intervals[endIndex][1] if intervals[endIndex][1] > newInterval[1] else newInterval[1]]
print(newNode)
frontNode = intervals[0:startIndex]
endNode = intervals[endIndex + 1: len(intervals)]
print(frontNode, endNode)
return intervals[0:startIndex] + [newNode] + intervals[endIndex + 1: len(intervals)]
파이썬 테스트 코드 작성
이번부터는 테스트 코드도 작성해봐야겠다 싶어서 찾아보니 python에서는 기본적으로 assert라는 간단한 검증 구문을 기능으로 제공하고 있었다.
아래와 같이 테스트 코드를 작성하였다.
example1 = Solution()
example_result1 = example1.insert([[1, 3], [6, 9]], [2, 5])
print(example_result1)
assert example_result1 == [[1, 5], [6, 9]]
example2 = Solution()
example_result2 = example2.insert(
[[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])
print(example_result2)
assert example_result2 == [[1, 2], [3, 10], [12, 16]]
example3 = Solution()
example_result3 = example3.insert(
[], [5, 7])
print(example_result3)
assert example_result3 == [[5, 7]]
example4 = Solution()
example_result4 = example4.insert(
[[1, 5]], [6, 8])
print(example_result4)
assert example_result4 == [[1, 5], [6, 8]]
검증에 실패하면 아래와 같이 출력된다.
File "/algorithm/leetcode/57.insert_interval.py", line 20, in <module>
assert example_result1 is [[1, 5], [6, 9]]
AssertionError
expected를 보여주는것은 좋지만 그와 함께 실제로는 어떤 결과가 나왔는지도 보여줬다면 더 좋지 않을까 싶긴하다.
궁금한 점
from typing import List
코딩테스트 같은걸 할 때 라이브러리를 추가하지 못하게 하는걸로 알고 있는데 typing에 있는 List는 써도 되는건가 싶긴하다. 나중에 잘 아는 사람이 있다면 물어봐야겠다.
-> 써도 됨.
자바로 다시 풀기 (24.07.23)
Merge Intervals 문제 답안 응용하기
바로 전에 풀었던 Merge Intervals를 그대로 가져다 쓸 수 있을 것 같아서 해보았더니 통과 된다.
public int[][] insert(int[][] intervals, int[] newInterval) {
int[][] newIntervals = Arrays.copyOf(intervals, intervals.length + 1);
newIntervals[intervals.length] = newInterval;
return merge(newIntervals);
}
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
Deque<int[]> intervalDeque = new ArrayDeque<>();
intervalDeque.add(intervals[0]);
for(int i = 1; i < intervals.length; i++) {
int[] lastElement = intervalDeque.getLast();
int[] nextElement = intervals[i];
if (lastElement[1] >= nextElement[0]) {
int[] mergedElement = new int[]{
lastElement[0],
Math.max(lastElement[1], nextElement[1])
};
intervalDeque.removeLast();
intervalDeque.add(mergedElement);
} else {
intervalDeque.add(nextElement);
}
}
return intervalDeque.toArray(int[][]::new);
}
TC, SC
시간 복잡도는 O(n*logn) 공간 복잡도는 O(n) 이다. (결과를 반환하기 위해 생성된 int[][]는 고려하지 않는다.)
성능을 개선한 답안 (pointer 사용)
문제를 잘 읽어보면 intervals 의 경우 start를 기준으로 이미 정렬이 되어있다고 하였기 떄문에 따로 정렬을 해줄 필요는 없다. for loop 에서는 start, end pointer를 이용해서 어느 구간이 병합되는지 기억해두고, 최종적으로 병합을 진행한다.
start 가 -1 인 경우는 맨 오른쪽에 추가가 되어야 한다는 의미이고 end 가 -1 인 경우는 맨 왼쪽에 추가가되어야 한다는 의미이다. 그 외에는 병합이 발생한 것이므로 병합처리를 진행한다.
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int start = -1;
int end = -1;
for (int i = 0; i < intervals.length; i++) {
if (start == -1 && intervals[i][1] >= newInterval[0]) {
start = i;
}
if (newInterval[1] >= intervals[i][0]) {
end = i;
}
}
if (start == -1) {
int[][] newIntervals = Arrays.copyOf(intervals, intervals.length + 1);
newIntervals[intervals.length] = newInterval;
return newIntervals;
}
if (end == -1) {
int[][] newIntervals = new int[intervals.length + 1][2];
newIntervals[0] = newInterval;
System.arraycopy(intervals, 0, newIntervals, 1, newIntervals.length - 1);
return newIntervals;
}
int[][] newIntervals = new int[intervals.length - (end - start)][2];
if (start >= 0) {
System.arraycopy(intervals, 0, newIntervals, 0, start);
}
newIntervals[start] = new int[]{Math.min(intervals[start][0], newInterval[0]), Math.max(intervals[end][1], newInterval[1])};
if (intervals.length - (end + 1) >= 0) {
System.arraycopy(intervals, end + 1, newIntervals, end + 1 - (end - start), intervals.length - (end + 1));
}
return newIntervals;
}
}
TC, SC
시간 복잡도는 O(n) 공간 복잡도는 O(1) 이다. (결과를 반환하기 위해 생성된 int[][]는 고려하지 않는다.)
System.arraycopy
System.arraycopy 의 경우에는 (공식 문서) array의 data를 copy할 때 효율적으로 처리할 수 있지만, 개인적으로 api가 직관적이지는 못한 것 같다. 그래도 한 번 적용해보았다.