성능 요약
메모리: 618568 KB, 시간: 2504 ms
분류
자료 구조, 덱, 우선순위 큐
제출 일자
2023년 10월 14일 15:17:49
문제 설명
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 NumberFormatException, 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());
Deque<Node> deque = new LinkedList<>();
for (int i = 0; i < N; i++) {
int tmp = Integer.parseInt(st.nextToken());
while (!deque.isEmpty() && deque.getLast().value > tmp) {
deque.removeLast();
}
deque.addLast(new Node(i, tmp));
if (deque.getFirst().idx <= i - L) {
deque.removeFirst();
}
bw.write(deque.getFirst().value + " ");
}
bw.flush();
bw.close();
}
static class Node {
public int idx;
public int value;
Node(int idx, int value) {
this.idx = idx;
this.value = value;
}
}
}
'알고리즘 - Baekjoon > Platinum' 카테고리의 다른 글
[백준][Platinum V] 3015번 : 오아시스 재결합 - JAVA(자바) (0) | 2023.10.14 |
---|