[BOJ] [JAVA] 11003번 최소값 찾기

11003번: 최솟값 찾기

슬라이딩 원도우를 이용하여 풀려고 했으나 내가 계속 시도했던 방식은 최소값이 빠져나가면 다시 큐의 최소값을 찾는 방식이었기 때문에 시간 초과가 되었다.

큐에 배열을 넣고 푸는 방식으로 다시 풀었다.

며칠 전에 배웠던 모노 스택 개념과 유사하다고 느꼈다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		/*
		 * 모노스택 개념이라고 할 수 있을지 모르겠지만
		 * 모노스택을 생각하며 풀었다
		 * 
		 * 새로 들어오는 수를 '나'라고 할 때,
		 * 큐에 들어있는 나보다 큰 수를 모두 쳐낸 후 큐에 들어간다.
		 * -> 지금 들어온 나보다 큰 수는 어차피 출력되지 않을 것이기 때문.
		 * 
		 * 이렇게 되면 큐의 원소들은 오름차순으로 정렬된다.
		 * 
		 * 큐의 가장 앞 원소가 L이라는 시간이 흐른 후 제거될 수 있도록
		 * 큐에 들어온 시간을 함께 넣어준다. -> {원소값, 들어온 시간}
		 */
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		// 0번 인덱스 : 입력 값
		// 1번 인덱스 : 몇번째에 들어왔는지 확인할 인덱스 번호
		Deque<int[]> queue = new ArrayDeque<>();
		
		int D = Integer.MAX_VALUE;
		
		for (int i = 0; i < n; i++) {
			int k = Integer.parseInt(st.nextToken());
			while (!queue.isEmpty() && queue.peekLast()[0] >= k) {
				queue.pollLast();
			}
			
			queue.offer(new int[] {k, i});
					
			if (i - l == queue.peek()[1]) {
				queue.poll();
			}
			D = queue.peek()[0];
			sb.append(D).append(' ');
		}
		System.out.println(sb);
	}

}