LeetCode: 56번 (Merge Intervals) [JAVA]

문제 링크

https://leetcode.com/problems/merge-intervals/

Merge Intervals - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 우선 전체 int[][] intervals를 돌며, 구간의 최소와 최대값을 확인
2. 주어진 구간만큼의 크기를 2배하여 누적합을 위한 배열 생성
3. 다시 int[][] intervals를 돌며, 주어진 구간의 시작은 단순히 2배를 한 위치에 +1 처리를, 구간의 끝은 2배에 +1을 한 위치에 -1 처리를 진행
4. 전체 누적합 배열을 돌며 누적합 연산을 진행
5. 이후 다시 한 번 누적합 연산을 돌며, 구간의 시작과 끝의 1/2값을 List<List<Integer>>에 저장
6. 최종적으로 반환할 답의 타입에 맞게 int[][]을 초기화 후 답을 옮겨담아 반환

 문제를 처음 보았을 때 구간들의 연속을 체크하는데 누적합 연산을 바로 떠올렸지만, 문제 상의 예외 케이스로 좀 애를 먹었던 문제이다. 핵심 로직은 주어진 구간을 누적합을 사용해 구간의 시작과 끝을 각각 +1, -1 처리를 진행하고, 이후 해당 표시를 한 구간을 처음부터 돌며 현 위치의 값을 이전 위치의 값+현 위치의 값으로 다시 계산해주는 방식이다. 그렇게 되면 하나의 구간을 쭉 표시를 해주게 되며, 이 방식의 경우 여러 구간의 값이 주어질 때 해당 구간 표시를 할 때 드는 복잡도를 단 한 번의 배열을 도는 것으로 처리가 되며 시간 복잡도를 크게 줄일 수 있다. 이 방식의 경우 imos법이라는 이름으로도 유명하다.

 다만 해당 방식을 여기 문제 해결에 그대로 적용할 수는 없는데, 바로 구간의 시작과 끝이 동일한 경우가 존재하는 문제가 있다. 누적합을 사용하는 경우 시작 위치에 +1, 마지막 위치에 -1을 적용하는데, 이 경우 주어진 구간의 시작과 끝이 동일하면 이는 단순히 결과적으로 0이 되며, 해당 부분이 구간이었는 지를 확인할 수가 없다. 이를 해결하기 위해 구간을 늘려버리는 방식을 적용했는데, 주어진 구간을 2배로 늘리고 주어진 구간의 시작은 위치 값의 2배를 한 곳에, 구간의 끝은 위치 값의 2배+1을 한 곳에 체크를 하면, 시작과 끝을 구분지을 수 있다. 또한 추후 구간을 확인할 때 각 위치의 값을 절반으로 나누면, 둘이 같은 값으로 귀결되며 결국 구간 시작과 끝이 같을 때의 문제를 해결할 수 있다.
 결국 문제 해결에 있어 우선 주어진 intervals 배열을 돌며 구간의 최소값, 최대값을 확인하고, 누적합 연산을 위해 (최대값 - 최소값 +1) 구간의 2배를 배열의 크기로 선언한다. 그 다음엔 다시 intervals 배열을 돌며 구간의 시작과 끝을 각각의 값 2배와 2배+1을 한 곳에 +1, -1 처리를 해주고, 그 다음 누적합 배열을 돌며 누적합 연산을 진행한다. 이후에는 구간의 표시가 완료되며, 겹치는 구간이 있다면 해당 구간은 중간에 0이 없이 1이상의 값들로 연결되어 있을 것이다. 그렇게 누적합 연산이 완료된 누적합 배열을 돌며 구간의 시작과 끝을 체크해주고, (해당 값의 절반 + 구간 최소값)을 모두 List<List<Integer>>에 저장해준다. 그렇게 구간 저장이 완료되면 최종 답 반환을 위해, 크기에 맞게 int[][] 배열을 선언해주고 List<List<Integer>> 속 답을 옮겨 담아 반환해주면 된다.

 

class Solution {
    public int[][] merge(int[][] intervals) {
        int minNum = 100000, maxNum = 0;
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < intervals.length; i++) {//구간의 최소, 최대 확인
            minNum = Math.min(minNum, intervals[i][0]);
            maxNum = Math.max(maxNum, intervals[i][1]);
        }

        int[] imos = new int[(maxNum - minNum + 1) * 2];//특정 구간+1의 2배 크기를 누적합 구간으로 설정

        for (int i = 0; i < intervals.length; i++) {//주어진 시작과 끝의 비율을 조절하여 누적합 구간에 표시
            imos[(intervals[i][0] - minNum) * 2] += 1;
            imos[(intervals[i][1] - minNum) * 2 + 1] -= 1;
        }

        for (int i = 1; i < imos.length; i++) {//누적합 연산
            imos[i] = imos[i] + imos[i - 1];
        }

        int sectionStart = 0, sectionEnd;

        for (int i = 0; i < imos.length - 1; i++) {//구간 체크
            if ((i == 0 && imos[i] > 0) || (i > 0 && imos[i] > 0 && imos[i - 1] == 0)) {//시작 체크
                sectionStart = i;
            }

            if (imos[i] > 0 && imos[i + 1] == 0) {//끝 체크 후 저장
                sectionEnd = i + 1;
                result.add(List.of(sectionStart / 2 + minNum, sectionEnd / 2 + minNum));
            }
        }

        int[][] answer = new int[result.size()][2];

        for (int i = 0; i < result.size(); i++) {//답을 반환할 타입에 맞게 변환
            answer[i][0] = result.get(i).get(0);
            answer[i][1] = result.get(i).get(1);
        }

        return answer;
    }
}

결과