[백준11003] 최솟값 찾기 Java

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

package Chapter1;

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

public class BJ11003 {

    // Node는 인덱스와 해당 인덱스의 값을 갖고 있음
    static class Node {
        public int index;
        public int value;

        public Node(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }

    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());
        Deque<Node> dq = new ArrayDeque<>();

        for (int i=0; i<n; i++) {
            // 다음 저장 할 숫자
            int num = Integer.parseInt(st.nextToken());
            // Deque에 요소가 있는데, 제일 마지막에 있는 값이 새로 들어오는 값보다 크다면
            // 최소값을 구하려는 우리에게는 더 이상 필요없기 때문에 Deque에서 제거해준다
            while (!dq.isEmpty() && dq.getLast().value > num) {
                dq.removeLast();
            }
            // 더 작은 값은 Deque에 들어온다(맨뒤로)
            // 그렇게 되면 자연스럽게 Deque는 오름차순으로 정렬이 되기 시작한다
            // 즉 최소값은 Deque 안에 있는 원소를 출력하면 된다
            dq.offer(new Node(i, num)); // dq.addLast() 하면 시간초과

            // 하지만 윈도우의 크기는 3개여야 함.
            // 즉 맨 앞의 원소의 인덱스는 (맨 뒤 - 맨 앞)의 값보다 작아야함
            // 그래서 맨 첫 원소를 제거한다
            if (dq.getFirst().index <= i-l) {
                dq.removeFirst();
            }
            bw.write(dq.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }
}