(Leetcode) 56 - Merge Intervals 풀이
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/merge-intervals
내가 작성한 풀이
각 interval 을 start 를 기준으로 정렬한다. 이후 merge를 진행한다.
Deque는 Stack처럼 사용하려고 사용하였다. (사실 List여도 상관 없다.) Deque에 있는 마지막 Element와 다음에 추가하려고 하는 Element를 비교하여 merge할 수 있으면 merge 하고 그렇지 않으면 새로 Deque 에 추가한다.
class Solution {
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[][]는 고려하지 않는다.)