[Platinum V] 최솟값 찾기 - 11003 - JAVA[자바]

문제 링크

성능 요약

메모리: 618568 KB, 시간: 2504 ms

분류

자료 구조, 덱, 우선순위 큐

제출 일자

2023년 10월 14일 15:17:49

문제 설명

N개의 수 A₁, A₂, ..., A_N과 L이 주어진다.

D_i = A_i-L+1 ~ A_i 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 A_i는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 A_i가 주어진다. (-10⁹ ≤ A_i ≤ 10⁹)

출력

첫째 줄에 D_i를 공백으로 구분하여 순서대로 출력한다.

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;
        }
    }
}