배열과 리스트: 최솟값 찾기 (백준 11003)

 

 

난이도: 플레티넘 5

풀이: Java의 util 중 하나인 덱(deque)를 이용한다.

 

 

import java.util.*;
import java.io.*;
 
 
public class Q11003 {
    public static final Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N            = Integer.parseInt(st.nextToken());
        int L            = Integer.parseInt(st.nextToken());
        st                 = new StringTokenizer(br.readLine());
        
        Deque<Node> mydeque = new LinkedList<>();
        for (int i = 0; i < N; i ++) {
            int now = Integer.parseInt(st.nextToken());
            
            while (!mydeque.isEmpty() && mydeque.getLast().value > now) {
                mydeque.removeLast();
            }
            mydeque.addLast(new Node(now, i));
            if (mydeque.getFirst().index <= i - L) {
                mydeque.removeFirst();
            }
            bw.write(mydeque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }
        
        static class Node {
            public int value;
            public int index;
            
            Node(int value, int index){
                this.value = value;
                this.index = index;
            }
        }
}