BOJ - 11003 ) 최솟값 찾기

 

---

www.acmicpc.net/problem/11003

1717번: 집합의 표현

---

배열을 O(n)탐색하면서 현재 값보다 큰 값은 빼주고, index가 범위 밖에 있는것도 빼준다.

 

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class 최솟값찾기 {
	
	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()," ");
		StringBuilder sb = new StringBuilder();
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		int arr[] = new int[N];for(int i=0;i<N;i++)arr[i] = Integer.parseInt(st.nextToken());
		for(int i=0;i<N;++i) {
			while(!dq.isEmpty()&&dq.peekFirst()<=i-L) dq.removeFirst();
			while(!dq.isEmpty()&&arr[dq.peekLast()]>=arr[i]) dq.removeLast();
			dq.offer(i);
			sb.append(arr[dq.peek()]+" ");
		}
		bw.write(sb.toString());
		bw.flush();bw.close();

	}

}

---