LeetCode: 56번 (Merge Intervals) (JAVA)

문제 링크

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

풀

전반적인 릴리스 프로세스는 다음과 같습니다.

1. 우선, 전체의 int()() intervals 를 돌려, 구간의 최소와 최대치를 확인
2. 주어진 구간만의 크기를 2배로 하여 적층하기 위한 배열을 작성한다
3. 다시 int()() intervals 를 돌려, 주어진 구간의 개시는 단순히 2배를 한 위치에 +1 처리를, 구간의 끝은 2 배에 +1 을 한 위치에 -1 처리를 진행한다
4. 전체 적산 배열을 돌려 적산 연산을 진행
5. 그런 다음 다시 누적 연산을 돌려 구간의 시작과 끝의 절반 값을 List>에 저장
6. 최종적으로 돌려주는 대답의 타입에 맞도록 int()() (을)를 초기화 후, 대답을 옮겨놓아 돌려준다

문제를 처음 보았을 때 구간의 연속을 체크하는데 누적 연산을 곧바로 떠올렸지만 문제상의 예외 케이스에서 조금 고생한 문제다.

코어 로직은 주어진 구간을 누적을 이용하여 구간의 시작과 끝을 각각 +1, -1 처리를 진행하고, 이후 해당 표시를 한 구간을 처음부터 돌려 현재 위치의 값을 전위치의 값 +현 위치의 값으로 재계산하는 방식이다.

그렇게 되면 1개의 구간을 계속 표시해 주게 되고, 이 방식의 경우, 복수의 구간의 값이 주어졌을 때에 그 구간 표시를 할 때에 걸리는 복잡도를 1회의 배열을 돌리는 것으로 처리가 되어 시간 복잡도를 크게 줄일 수 있다.

이 방식의 경우, imos법이라는 이름으로도 유명합니다.

다만, 그 방식을 여기의 문제해결에 그대로 적용할 수는 없지만, 바로 구간의 시작과 끝이 같은 경우가 존재하는 문제가 있다.

누적을 사용하는 경우 시작 위치에 +1, 마지막 위치에 -1을 적용합니다.

이 경우 주어진 구간의 시작과 끝이 같으면 단순히 결과가 0이 되고 그 부분이 구간인지 여부를 확인할 수 없습니다.

이를 해결하기 위해 구간을 늘려 버리는 방식을 적용했지만, 주어진 구간을 2배로 늘려 주어진 구간의 시작은 위치값의 2배를 1개소로, 구간의 끝은 위치값 의 2배+1을 1개소에 체크하면, 개시와 종료를 구별할 수 있다.

또, 후의 구간을 확인할 때에 각 위치의 값을 반으로 나누면, 2개가 같은 값으로 귀결해, 결국 구간의 개시와 종료가 같을 때의 문제를 해결할 수 있다.


결국 문제 해결에서 먼저 주어진 intervals 배열을 돌려 구간의 최소값, 최대값을 확인하고, 누적 연산을 위해 (최대값-최소값 +1) 구간의 2배를 배열 크기로 선언 한다.

그럼 다시 intervals 배열을 돌려, 구간의 시작과 끝을 각각의 값의 2배와 2배+1을 1개소에 +1, -1 처리를 하고, 다음에 누적 배열을 돌려 누적 연산을 진행시킨다.

그러면 구간 표시가 완료되고 중복 구간이 있는 경우 그 구간은 중간에 0 없이 하나 이상의 값으로 연결되어야 합니다.

이와 같이 누적 연산이 완료된 누적 배열을 돌려 구간의 시작과 끝을 체크하고 (해당 값의 절반 + 구간 최소값)을 모두 List>에 저장합니다.

그렇게 구간 저장이 완료되면, 최종 대답을 반환하기 위해 크기에 맞게 int()() 배열을 선언합니다.

목록> 안의 대답을 옮겨 돌려주면 된다.

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;
    }
}

결과