[BOJ 11003] 최솟값 찾기(Deque)

www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

 

## 접근

---

특정 구간이라는 단어를 보면 세그먼트 트리를 습관적으로 이용하려고 했다. N * logN의 시간복잡도를 가지므로 나쁘지 않은 선택이지만 이 문제에서 시간 초과가 발생한다. 이 문제는 세그먼트 트리와 다르게 고정된 길이의 구간의 값들의 최솟값을 요구하고 있다.

 

 

 

세그먼트 트리보다 더 빠르게 최소값을 찾을 수 있지 않을까? 최소값을 바로 얻을 수 있는 자료구조가 필요하다. 특정 자료구조는 현재의 최솟값과 구간이 이동함에 따라서 필요한 미래의 최솟값도 가지고 있어야 한다.

 

 

 

자료구조는 값이 정렬된 상태로 유지되어야 구간이 이동함에 따라서 원하는 최솟값을 얻을 수 있다. 정렬된 상태를 유지하기 위해서, 값이 들어갈 때 자료구조에서 가장 큰 값이 되어야 한다. 값이 들어갈 때, 자료구조내에 더 큰 값들은 절대로 최솟값의 후보가 될 수 없으므로, 제거해줘야 한다.

 

 

 

우리가 필요한 자료구조의 정의는 최솟값들의 후보의 정렬된 상태이다. 또한, 특정한 구간을 요구하고 있어 구간이 벗어나면 해당 아이템은 제거해야 한다.

 

 

 

위의 생각을 바탕으로 코드를 작성하면 된다.

 

## 해설코드

---

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, L;
    static Deque<Item> deq = new ArrayDeque<>();
    static String[] sArr;
    static int[] result;
    static class Item{
        int idx, val;
        Item(int idx, int val){
            this.idx = idx;
            this.val = val;
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        sArr = br.readLine().split(" ");
        
        N = Integer.valueOf(sArr[0]);
        L = Integer.valueOf(sArr[1]);
    
        sArr = br.readLine().split(" ");
        
        result = new int[N + 1];
        
        for(int i = 1; i <= sArr.length; i++){
            int num = Integer.valueOf(sArr[i - 1]);
            
            if(!deq.isEmpty() && deq.peekFirst().idx <= i - L)
                deq.pollFirst();
                
            while(!deq.isEmpty() && deq.peekLast().val >= num)
                deq.pollLast();
            
            deq.offer(new Item(i, num));
            result[i] = deq.peekFirst().val;
        }
        
        for(int i = 1; i <= N; i++)
            bw.write(result[i] + " ");
        
        bw.flush();
        bw.close();
        br.close();
    }
}