박종훈 알고리즘 블로그

(Leetcode) 56 - Merge Intervals 풀이

기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice


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[][]는 고려하지 않는다.)

categories: 스터디-알고리즘

tags: 자바 , java , 리트코드 , Leetcode , 알고리즘 , interval , array , merge