[Java] 11003 최솟값 찾기

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

 

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

 

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

 

import java.io.*;
import java.util.*;

public class Main{
	public static void main(String[] args) throws IOException {
        
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        
		int num = Integer.parseInt(stringTokenizer.nextToken());
		int scope = Integer.parseInt(stringTokenizer.nextToken());
		stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		Deque<Node> myDeque = new LinkedList<>();
        
		for(int i =0 ; i<num; i++) {
			int now = Integer.parseInt(stringTokenizer.nextToken());
			while(!myDeque.isEmpty() && myDeque.getLast().value > now) {
				myDeque.removeLast();
			}
			myDeque.addLast(new Node(now, i));
			if(myDeque.getFirst().index <= i-scope) {
				myDeque.removeFirst();
			}
			bufferedWriter.write(myDeque.getFirst().value + " ");
		}
		bufferedWriter.flush();
		bufferedWriter.close();
	}
	static class Node {
		public int value;
		public int index;	
		Node(int value, int index) {
			this.value = value;
			this.index = index;
		}
	}
}