[Grind75-LeetCode] Merge Intervals JAVA

반응형

728x90

[Grind75-LeetCode] Merge Intervals - Medium 

---

접근

• 구현

---

풀이

2차원 배열로 구간이 주어지면 겹치는 구간을 합쳐 반환하는 문제이다. 이전에 풀었던 구간 삽입 문제와 비슷한 듯 다른 문제이다. 

intervals = [[1,3],[2,6],[8,10],[15,18]] -> intervals = [[1,6],[8,10],[15,18]]
1~3 + 2~6 병합 -> 1~6

위와 같이 구간이 들어있는 배열이 존재할 때 겹치는 범위를 병합하여 병합된 배열을 반환하는 문제이다. 내가 풀었던 방법을 먼저 설명하고 더 성능이 좋았던 다른 코드를 몇 개 들고 와 분석할 예정이다.

    public int[][] merge(int[][] intervals) {
        List<int[]> result = new ArrayList<>();
        Arrays.sort(intervals, (a,b) -> a[0]-b[0]);

        int start = intervals[0][0];
        int end = intervals[0][1];

문제를 풀기 위해 주어진 배열을 정렬해 주었다. 시작 범위가 작은 순으로 정렬해 넓은 범위로 병합이 가능하다. 배열에 순서대로 접근하며 병합해 나가기 때문에 끝나는 범위를 기준으로 정렬할 경우 [2,3], [5,6], [1,10]처럼 제일 넓은 범위에 마지막에 접근할 수 있기에 정확한 병합이 불가능하다. 그리고 병합 범위 관리를 위해 시작 값과 끝 값을 저장할 변수를 선언했다. 

	for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= end) {
                end = Math.max(end, intervals[i][1]);
            } else {
                result.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }

시작 값과 끝 값을 0번 인덱스의 값으로 초기화했기 때문에 순회는 1번 인덱스부터 시작하게 된다. 범위 1의 시작 값이 범위 0의 끝 값 보다 작거나 같은 경우 범위 0 내에 범위 1의 시작 값이 존재하므로 범위 0과 범위 1은 병합되게 된다. 병합이 되는 경우 병합된 범위의 끝 값은 범위 0과 범위 1의 끝 값 중 더 큰 값으로 설정된다. 만약 범위 1의 시작 값이 범위 0의 끝 값 보다 큰 경우 병합이 불가능한 개별 범위를 가지고 있으므로 시작과 끝 포인터를 다음 범위로 옮기게 된다. 

	result.add(new int[]{start, end});

        return result.toArray(new int[result.size()][]);
    }

순회가 끝난 시점 마지막 범위에 대한 삽입은 되지 않은 상태이기 때문에 마지막 범위를 리스트에 넣어주고 2차원 배열로 변환해 반환한다. 

기본

이 문제도 테스트 케이스가 달라져 결과가 7~11ms 정도까지 뒤죽박죽이다. 대부분 평균 시간 내에 존재하는 코드들은 거의 비슷한 방법으로 해결되었고 우선순위 큐를 이용해 푼 방법도 있었는데 배열을 정렬하는 대신 우선순위 큐에 넣는 것 외에는 다른 내용이 없어 제일 빠른 시간으로 풀어진 코드를 가져왔다. 

---

0ms 코드

0ms의 시간으로 통과되었던 코드로 배열에 각 범위의 시작 값과 끝 값을 기록해 두고 해당 배열을 이용해 병합된 배열을 만드는 방법이다. 

    public static int[][] merge(int[][] intervals) {
        int max = 0;
        for (int i = 0; i < intervals.length; i++) {
            max = Math.max(intervals[i][0], max);
        }

        int[] mp = new int[max + 1];
        for (int i = 0; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            mp[start] = Math.max(end + 1, mp[start]);
        }

우선 배열을 순회하며 시작점 중 가장 큰 값을 찾아 해당 크기보다 1 큰 배열을 만든다.  시작 값은 0부터 존재하고 해당값의 인덱스 접근을 위해 1 큰 배열을 만드는 것이다. 만들어진 배열에는 시작값을 인덱스로 사용해 시작값 인덱스 내 해당 범위의 끝 값을 저장한다. 범위가 [1,6]이라면 배열 1번 인덱스에 6이라는 끝 값이 저장되는 것이다. Math.max를 이용해 항상 해당 인덱스 내 존재하는 끝 값은 최댓값을 유지하게 한다. end + 1을 하여 저장하는 것은 범위에 0이 포함된 경우 처리를 위함도 있고 범위 관리를 편하게 하기 위함도 있는 거 같은데 현재 코드에선 0이 포함된 경우 처리를 위해 저렇게 한 것 같다.

	int r = 0;
        int have = -1;
        int intervalStart = -1;
        for (int i = 0; i < mp.length; i++) {
            if (mp[i] != 0) {
                if (intervalStart == -1) intervalStart = i;
                have = Math.max(mp[i] - 1, have);
            }
            if (have == i) {
                intervals[r++] = new int[] { intervalStart, have };
                have = -1;
                intervalStart = -1;
            }
        }

만들어진 배열을 순회하며 병합 배열을 만드는 과정이다. r은 병합 배열을 만드는 데 사용할 인덱스 변수이고 have는 현재 최대 끝 값을 저장할 변수 intervalStart 변수는 현재 구간 시작 값을 나타낸다. 배열을 순회하며 배열의 인덱스 값이 0이 아니라면 해당 구간이 존재한다는 의미로 만약 현재 시작 값이 -1일 경우 해당 인덱스는 새로운 범위 시작으로 intervalStart의 값을 해당 인덱스로 바꿔주고 끝 값을 해당 인덱스에 저장되어 있는 값으로 업데이트한다. end + 1로 저장되었기 때문에 -1을 해주어 범위를 맞춰준다. 만약 현재 인덱스가 저장되어 있는 끝 값과 같다면 해당 범위를 배열에 추가해 주고 시작 값과 끝 값을 다시 -1로 변경해 현재 탐색 중인 범위가 없다는 것을 알린다. 

	if (intervalStart != -1) {
            intervals[r++] = new int[] { intervalStart, have };
        }

        if (intervals.length == r) {
            return intervals;
        }

        int[][] res = new int[r][];
        for (int i = 0; i < r; i++) {
            res[i] = intervals[i];
        }
        return res;

순회가 끝나고 현재 시작 인덱스가 -1이 아니라면 병합 중이던 범위가 있는 것으로 해당 범위를 추가해 주고 만들어진 배열이 병합 전 배열과 같다면 바로 병합 배열을 반환하고 병합된 범위가 있어 배열의 크기가 줄어들었다면 해당 범위까지의 배열을 새로 만들어 반환한다.  

0ms

 

---

전체 코드

기본

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> result = new ArrayList<>();
        Arrays.sort(intervals, (a,b) -> a[0]-b[0]);

        int start = intervals[0][0];
        int end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= end) {
                end = Math.max(end, intervals[i][1]);
            } else {
                result.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        result.add(new int[]{start, end});

        return result.toArray(new int[result.size()][]);
    }
}

 

0ms

class Solution {
    public static int[][] merge(int[][] intervals) {
        int max = 0;
        for (int i = 0; i < intervals.length; i++) {
            max = Math.max(intervals[i][0], max);
        }

        int[] mp = new int[max + 1];
        for (int i = 0; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            mp[start] = Math.max(end + 1, mp[start]);
        }

        int r = 0;
        int have = -1;
        int intervalStart = -1;
        for (int i = 0; i < mp.length; i++) {
            if (mp[i] != 0) {
                if (intervalStart == -1) intervalStart = i;
                have = Math.max(mp[i] - 1, have);
            }
            if (have == i) {
                intervals[r++] = new int[] { intervalStart, have };
                have = -1;
                intervalStart = -1;
            }
        }

        if (intervalStart != -1) {
            intervals[r++] = new int[] { intervalStart, have };
        }

        if (intervals.length == r) {
            return intervals;
        }

        int[][] res = new int[r][];
        for (int i = 0; i < r; i++) {
            res[i] = intervals[i];
        }

        return res;
    }
}