OJ
[BOJ] 11003 최솟값 찾기 (JAVA)
P3PP4
2023. 4. 30. 10:00
https://www.acmicpc.net/problem/11003
11003번: 최솟값 찾기
N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
www.acmicpc.net
이크.. 에크.. 데크..
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int N, L, num;
static ArrayDeque<int[]> dq = new ArrayDeque<>();
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
num = Integer.parseInt(st.nextToken());
while (!dq.isEmpty() && num < dq.peekLast()[1]) dq.pollLast();
dq.offer(new int[] { i, num });
if (dq.peek()[0] <= i - L) dq.poll();
sb.append(dq.peek()[1]).append(" ");
}
System.out.print(sb);
}
}