리트코드 - 56. Merge Intervals

리트코드 - 56. Merge Intervals

출처 - https://leetcode.com/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 배열은 internals=[starti, endi]로 표현됩니다. 겹치는 모든 간격들을 병합하고, 입력된 모든 간격을 커버하는 겹치지 않는 간격들의 배열을 반환하세요.

 

풀이코드

class Solution {
    public int[][] merge(int[][] intervals) {
        int length = intervals.length;
        if (length <= 1) {
            return intervals;
        }

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        List<int[]> result = new ArrayList<>();
        int[] curInterval = intervals[0];
        result.add(curInterval);

        for (int[] interval : intervals) {
            int curEn = curInterval[1];
            int nSt = interval[0];
            int nEn = interval[1];

            if (curEn >= nSt) {
                curInterval[1] = Math.max(curEn, nEn);
            } else {
                curInterval = interval;
                result.add(curInterval);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

코드설명

문제를 요약하면 여러개의 범위가 주어졌을때, 그 범위를 모두 덮는 요소로만 리턴하는 문제이다.

수학에서 집합관계와 비슷하다. 일부만 교집합이 있다면 전체는 합집합이 될 것이고, 어느 하나가 포함된다면 큰 집합으로 표현 될 것이다.

따라서 교집합이 있는 경우와 없는 경우로 분리하여 생각해보았다.

 

1. 교집합이 있다면    

  1-1. 교집합이 일부인가  -> 두 집합에서 제일 작은값이 시작점, 제일 큰 값이 끝점 범위가 된다.

  1-2. 교집합이 작은 집합 그 자체 -> 두 집합 중 범위가 큰 집합의 시작점과 끝점이 범위가 된다.

2. 교집합이 없다면  -> 원래의 두 개의 배열 요소를 반환한다.

 

이렇게 두 개의 배열 요소를 검증하면 될 것인데 다음 요소들을 검증할 때가 번거로워진다.

앞에서 이미 검증한 범위의 값이 나왔는데 또 그 값을 검증하려면 처리하기가 귀찮아진다.

예를 들어 (2,3), (6,8)를 검증하여 (2,3), (6,8)을 만들었는데, 다음 요소에서 (2,5)가 나오면 다시 처리하기가 귀찮아진다.

 

따라서 이것을 해결하기 위해 시작점을 기준으로 정렬을 미리하여 앞에서 정렬해주면 된다.

던, 2차원 배열이므로 정렬값을 지정해주어야 한다.

오버로딩 된 Arrays.sort(배열, 정렬기준)함수를 사용하여 정렬하고, 기준은 Comparator.comparingInt(a -> a[0]) 를 이용해 첫번째 값을 기준으로 한다.

이렇게 정렬하면 (2,3), (2,4), (3,6), (5, 7) 이런식의 입력값에도 앞에서 검증한 범위안에서 해결이 가능하다.

처음에 (2,4)로 합쳐질 것이고, 이 범위 안에서 두번째 배열 3이 시작되므로 (2,6)이 될 것이다.

---

이제 정렬을 했으면 본격적으로 코드를 짜보자.

자료형은 List<int[]> 배열을 사용했는데, 장점이 뭘까?

 

이렇게 하면 List자료형에다가 배열을 미리 넣고 조작이 가능해진다.

int[] curInterval = intervals[0];
result.add(curInterval);

첫번째 배열을 기준값으로 정한 다음, 반복문을 돌린다.

이미 첫번째 요소로 오름차순 되었기 때문에 (a,b)에서 끝 값인 b만 검증이 들어가면 된다.

 

첫번째 요소를 (a1,b1) 두번째 요소를 (a2,b2)라고 한다면

1. b1이 뒤 배열의 a2보다 같거나 크다면 교집합이 존재한다. 따라서 b1이나 b2중 큰 수가 범위의 끝이 된다.

2.b1이 뒤 배열의 a2보다 작으면 겹치는 범위가 없다. 따라서 기준값을 현재 (a2,b2) 배열로 갱신해주면 된다.

 

설명을 위해 a1,b1으로 헀는데 코드에서는 b1이 curEn이고, nSt 가 a2이고, nEn 이 b2이다.

이렇게 하고 List를 2차원 배열로 만들기 위해 toArray를 써주면 해결된다.

 

시간복잡도 - O(NlogN) (정렬에 사용되는 시간)

공간복잡도 - O(N)

 

정리

이차원 배열을 다듬어서 다시 이차원 배열로 반환하는 방법