[LeetCode] 57. Insert Interval - 유니온파인드(UnionFind) OR 구현(Implementation) JAVA

https://leetcode.com/problems/insert-interval/description/

코드설명

유니온파인드(UnionFind) OR 구현(Implementation) 를 활용합니다.

 

각 구간을 집합으로 살펴보고, 합치는 과정을 진행합니다.

이 방식으로 진행할 경우, 만약 interval이 [0,0] 이면 visited로 이 경우도 포함하도록 해야하는등 신경써야할 부분이 많습니다.

 

그대신에, 정답코드2번으로 진행합니다.

풀이는 아래와 같습니다.

current의 start, end 가 존재. interval 의 start, end가 존재. (이떄 interval은 current의 오른쪽에 존재하는 list를 의미)

만약 current.end >= interval.start 라면, 서로 포함되어 있는 상태이므로 current.end = Math.max(current.end, interval.end)로 범위를 갱신합니다. 이때 Max 함수를 사용하는 이유는, [3,5], [4,8] [6,7] 로 테스트해보면 알 수 있습니다.

-> [3, 8] [6, 7]

-> [3, 7] -> 더 작아지는 상황발생.

current[1] = Math.max(current[1], interval[1]);

이렇게 작성하면, 예외처리해야하는 경우가 없어집니다.

코드

유니온 파인드를 활용한 정답코드1입니다.

처음에 접근한 방식입니다. 상호배타적 집합 개념을 활용하여, 각 Interval을 집합으로 의식하면 해결가능합니다.

class Solution {
    int[] parent = new int[100001];
    boolean[] visited = new boolean[100001];
    int minStart = 100001;
    int maxEnd = 0;
    public int[][] insert(int[][] intervals, int[] newInterval) {
        minStart = Math.min(minStart, newInterval[0]);
        maxEnd = Math.max(maxEnd, newInterval[1]);
        for(int i=0; i<parent.length; i++){
            parent[i] = i;
        }

        for(int i=0; i<intervals.length; i++){
            int start = intervals[i][0];
            int end = intervals[i][1];
            visited[start] = true;
            minStart = Math.min(minStart, start);
            maxEnd = Math.max(maxEnd, end);
            for(int j=start + 1; j<= end; j++){
                visited[j] = true;
                unionParent(start, j);
            }
        }

        int start = newInterval[0];
        int end = newInterval[1];
        visited[start] = true;
        for(int i=start + 1; i<=end; i++){
            visited[i] = true;
            unionParent(start, i);
        }

        for(int i=0; i<parent.length; i++){
            findParent(i);
        }
        ArrayList<int[]> answer = new ArrayList<>();
        int left = minStart;
        while(left <= maxEnd){
            int right = left;
            int[] newArr = new int[2];
            newArr[0] = left;
            while(right <= maxEnd && parent[right] == parent[right + 1]){
                right++;
            }
            newArr[1] = right;
            if(left != right || (visited[left] == true) ) {
                answer.add(newArr);
            }
            left = right;
            left++;
        }
        return answer.toArray(new int[answer.size()][]);   
    }

    int findParent(int x){
        if(parent[x] == x) return x;
        return parent[x] = findParent(parent[x]);
    }

    void unionParent(int a, int b){
        a = findParent(a);
        b = findParent(b);
        if(a < b) parent[b] = a;
        else if(b > a) parent[a] = b;
    }

}

 

정답코드2입니다.

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> intervalList = new ArrayList<>(Arrays.asList(intervals));
        intervalList.add(newInterval);
        Collections.sort(intervalList, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                return Integer.compare(o1[0], o2[0]);
            }
        });

        List<int[]> res = new ArrayList<>();
        int[] current = intervalList.get(0);

        for(int i=1; i<intervalList.size(); i++){
            int[] interval = intervalList.get(i);

            if(current[1] >= interval[0]){
                current[1] = Math.max(current[1], interval[1]);
                // current[1] = interval[1];
            } else {
                res.add(current);
                current = interval;
            }
        }

        res.add(current);
        return res.toArray(new int[res.size()][]);
    }
}