boj 11003: 최솟값 찾기

구하려고 하는 구간의 크기가 L로 결정되어 있을 때, 

모든 크기 L인 구간의 최솟값을 구하는 것이 sliding window 문제이다.

(세그먼트 트리나 다이나믹 프로그래밍 등으로도 풀 수 있다)

 

이 문제를 풀기 위해서는 덱을 이용해서 푸는데, 덱에 값과 인덱스를 저장한다.

덱에는 최대 L개의 값을 저장하고, 덱에 들어있는 값은 항상 증가하는 순서대로 저장한다.

 

• 덱은 값이 증가하는 순서로 저장되어 있다 --> 가장 처음 값이 최소값이다.
• 가장 처음 값의 인덱스와 현재 값의 인덱스의 차이가 L보다 큰지 작은지 검사한다.
• 가장 마지막 값이 현재 값보다 큰지 작은지 검사한다.
  • 덱의 마지막 값이 현재 값보다 크면 덱에서 제거하고 현재 값을 넣는다.

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

public class Main {
	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;
        
        st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int l=Integer.parseInt(st.nextToken());
		int arr[]=new int[n];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		Deque<Node> deque=new ArrayDeque<Node>();
		for(int i=0;i<n;i++) {
			int currentValue=arr[i];
			
			if(!deque.isEmpty() && deque.getFirst().index <=i-l) {
				// 최솟값이 될 수 없는 경우: 인덱스 차이가 넘 크다
				deque.pollFirst();
			}
			
			while(!deque.isEmpty() && deque.getLast().value>currentValue) {
				// 최솟값이 될 수 없는 경우: 값이 넘 크다
				deque.pollLast();
			}
			
			deque.offer(new Node(currentValue, i));
			arr[i] = deque.getFirst().value;
		}
		
		for(int i=0;i<n;i++) {
			bw.write(arr[i] + " ");
		}
		
		bw.flush();
		bw.close();
	}
}
class Node{
	int value;
	int index;
	
	public Node(int value, int index) {
		this.value=value;
		this.index=index;
	}
}