꿀잠

https://leetcode.com/problems/minimum-interval-to-include-each-query/description/

주어진 구간의 사이즈에 대하여 주어진 쿼리 값이 포함되는 구간 중 가장 작은 구간을 찾는 문제이다. 다양한 방식으로 문제 풀이를 시도하다 시간 초과를 통과하지 못했다. 문제의 Discussion 부분을 참조하여 다른 사람들의 의견들을 보던 중 세그먼트 트리 알고리즘에 대해 알게 되었다.

관련하여 블로그들을 보며 공부했다. 해당 알고리즘은 특정 구간의 대한 값들을 구간 기준으로 저장하는 트리에 대한 내용이었다. 루트 노드를 전체 구간으로, 자식 노드는 mid 값을 기준으로 구간을 반씩 나누며 구간에 대한 값을 저장하는 방식이었다. 해당 문제에선 주어진 구간의 size 값을 저장하고 최소 값을 기준으로 답을 찾아야 했기에 해당 알고리즘을 이용하여 풀이해 보았다.

트리의 구간은 문제에서 주어진 최대값을 기준으로 트리를 구성한 이후, 세그먼트 트리를 수정 하는 메서드, 값을 찾는 메서드를 완성해주었다. 이 후 아래의 코드를 완성하여 통과 할 수 있었다.

import java.util.*;  
  
public class Solution {  
  
    int[] sgTree;  
  
    public int[] minInterval(int[][] intervals, int[] queries) {  
  
        int min = 1;  
        int max = 10_000_000;  
        int treeSize = (max - min) * 4;  
        sgTree = new int[treeSize];  
        Arrays.fill(sgTree, max);  
        for(int[] interval : intervals){  
            int left = interval[0];  
            int right = interval[1];  
            int size = right - left + 1;  
            updateTree(1, min, max, left, right, size);  
        }  
  
        int[] answer = new int[queries.length];  
        for(int i = 0; i < queries.length; i++){  
            int size = queryTree(1, min, max, queries[i]);  
            answer[i] = size == max ? -1 : size;  
        }  
        return answer;  
    }  
  
    private void updateTree(int index, int start, int end, int left, int right, int size){  
        if(right < start || left > end){  
            return;  
        }  
  
        if(start >= left && end <= right){  
            sgTree[index] = Math.min(sgTree[index], size);  
            return;  
        }  
  
        int mid = start + (end - start) / 2;  
        updateTree(index * 2 ,start, mid, left, right, size);  
        updateTree(index * 2 + 1, mid + 1, end, left, right, size);  
    }  
  
    private int queryTree(int index, int start, int end, int find){  
        if((start == end)){  
            return sgTree[index];  
        }  
  
        int result = sgTree[index];  
  
        int mid = start + (end - start) / 2;  
        if(mid >= find){  
            result = Math.min(result, queryTree(index * 2, start, mid, find));  
        }else{  
            result = Math.min(result, queryTree(index * 2 + 1, mid + 1, end, find));  
        }  
  
        return result;  
    }  
  
}

하지만 문제를 통과한 이후에 속도가 다른 정답에 비해 떨어지는 것을 확인했다. 다른 솔루션들을 확인할 결과 세그먼트 트리를 사용하지 않는 방식이 더욱 효율적이었다. 각 구간의 값과 쿼리의 값 모두 최소값으로 정렬하고 PriorityQueue를 통하여 하나씩 뽑는 방식이었다. 해당 코드의 방식은 아래와 같다.

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[][] reorderQueries = new int[queries.length][2];
        for(int i = 0; i < queries.length; i++) {
            reorderQueries[i][0] = queries[i];
            reorderQueries[i][1] = i;
        }
        Arrays.sort(reorderQueries, (a, b) -> a[0] - b[0]);
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> (a[1] - a[0]) - (b[1] - b[0]));
        int i = 0;
        int[] results = new int[queries.length];
        Arrays.fill(results, -1);
        for(int[] query : reorderQueries) {
            while(i < intervals.length && query[0] >= intervals[i][0]) {
                queue.offer(intervals[i]);
                i++;
            }
            while(!queue.isEmpty() && queue.peek()[1] < query[0]) {
                queue.poll();
            }
            if(!queue.isEmpty()) {
                results[query[1]] = queue.peek()[1] - queue.peek()[0] + 1;
            }            
        }
        return results;
    }
}

비록 문제는 비효율적으로 풀었으나, 세그먼트 트리라는 새로운 알고리즘을 공부할 수 있었다.

(start, end)로 이루어진 구간 배열에서 서로 겹치지 않는 구간들만 남기기 위하여 지워야 하는 최소 원소의 개수를 구하는 문제이다. 구간의 겹침은 2번 구간의 시작 점이 1번 구간의 끝 지점 앞에 있다면 겹친다고 할 수 있다. 그리고 두 구간이 겹친다면 범위가 더 좁을 수록 좋다고 할 수 있다

.

구간을 효율적으로 비교하기 위하여 시작 지점을 기반으로 정렬한 이후 현재 위치보다 뒤에 있는 배열을 비교하며 체크해 주었다. 아래는 통과한 코드이다.

import java.util.*;  
  
class Solution {  
    public int eraseOverlapIntervals(int[][] intervals) {  
        Arrays.sort(intervals, (a, b) -> {  
            return Integer.compare(a[0],b[0]);  
        });  
  
        int answer = 0;  
        boolean[] removed = new boolean[intervals.length];  
        for(int i = 0; i < intervals.length - 1; i++){  
            if(removed[i]) continue;  
  
            int[] itv1 = intervals[i];  
            for(int j = i + 1; j < intervals.length; j++){  
                if(removed[j]) continue;  
  
                int[] itv2 = intervals[j];  
                if(itv2[0] < itv1[1]){  
                    answer++;  
                    if(itv1[1] > itv2[1]){  
                        removed[i] = true;  
                        break;  
                    }  
                    removed[j] = true;  
                }  
            }  
        }  
  
        return answer;  
    }  
}

하지만 이보다 더 효율적인 속도가 나오는 코드들이 있어 확인했다. 내가 해결한 코드의 경우 제거한 이후에는 removed 배열을 만들어 체크해주며 중복 체크를 피하고 있었다.

하지만 더 효율적인 속도의 코드의 경우 한번의 for문으로 해결하고 있었다. 각 요소를 한번만 체크하고 바로 제거할 것을 확인한 이후 다음 요소로 건너가는 방법이었다. 이 때 비교 군은 변수에 저장하여 유지하는 방식이었다. 그 방법은 아래와 같다.

```java
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        
        Arrays.sort(intervals , (a,b) -> a[0]-b[0]);
        int s1 = intervals[0][0];
        int e1 = intervals[0][1];
        int cnt = 0;

        for(int i=1;i<intervals.length;i++){

            int s2 = intervals[i][0];
            int e2 = intervals[i][1];

            if(e1 > s2){
                cnt++;
                s1 = s1;
                e1 = Math.min(e1,e2);
                continue;
            }

            s1 = s2;
            e1 = e2;
        }
        return cnt;
    }
}

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

이전에 풀었던 Merge Intervals 문제와 거의 같은 문제이다. 단 두번째 매개변수로 하나의 Intervals를 추가해주어야 한다. 이전에 풀었던 방식에서 PriorityQueue에 신규 Intervals 만 추가해 주면 문제를 해결할 수 있었다. 이전에 풀었던 Merge Intervals는 아래와 같다.

https://blog.honey-sleep.co.kr/61

최종 코드는 아래와 같다.

public class Solution {  
    public int[][] insert(int[][] intervals, int[] newInterval) {  
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0] );  
        for(int[] interval:intervals){  
            pq.add(interval);  
        }  
        pq.add(newInterval); // newInterval 을 넣어준다.  
  
        List<int[]> newArray = new ArrayList<>();  
  
        while(!pq.isEmpty()){  
            int[] cur = pq.poll();  
            while(!pq.isEmpty() && pq.peek()[0] <= cur[1]){  
                int[] next = pq.poll();  
                cur[1] = Math.max(next[1], cur[1]);  
            }  
            newArray.add(cur);  
        }  
  
        int finalSize = newArray.size();  
        int[][] answer = new int[finalSize][2];  
  
        for(int i = 0; i < finalSize; i++){  
            answer[i][0] = newArray.get(i)[0];  
            answer[i][1] = newArray.get(i)[1];  
        }  
  
        return answer;  
    }  
}

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

간격들이 주어졌을 때 서로 겹칠 수 있는 간격이면 합쳐서 최대한 압축한 형태의 간격 집합을 정답으로 내는 문제이다.

두 간격이 있을 때 겹친다고 하는 것은 앞 간격의 끝 값이 뒷 간격의 첫 값을 넘어서면 된다고 정의할 수 있다.

이 때 비교하는 두 간격을 정하기 위해서 간격의 앞 부분을 기준으로 순서대로 나열하면 차례대로 비교할 수 있다고 생각하고 PriorityQueue를 사용하였다. PriorityQueue에 간격 값들을 넣은 후 하나 씩 꺼내서 이어질때까지 잇는 작업을 while 문을 통해 진행한 이후 정답 List에 넣어 주었다. 최종적으로 배열화하여 return 하였다.

import java.util.*;  
  
public class Solution {  
    public int[][] merge(int[][] intervals) {  
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0] );  
        for(int[] interval:intervals){  
            pq.add(interval);  
        }  
  
        List<int[]> newArray = new ArrayList<>();  
  
        while(!pq.isEmpty()){  
            int[] cur = pq.poll();  
            while(!pq.isEmpty() && pq.peek()[0] <= cur[1]){  
                int[] next = pq.poll();  
                cur[1] = Math.max(next[1], cur[1]);  
            }  
            newArray.add(cur);  
        }  
  
        int finalSize = newArray.size();  
        int[][] answer = new int[finalSize][2];  
  
        for(int i = 0; i < finalSize; i++){  
            answer[i][0] = newArray.get(i)[0];  
            answer[i][1] = newArray.get(i)[1];  
        }  
  
        return answer;  
    }  
}