꿀잠

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

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