백준 11003번 최솟값 찾기 (Java)

문제

백준 11003번 최솟값 찾기 / 플래티넘5
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⁹)

풀이

범위 안의 최솟값을 연속해서 구하는 문제이다. 예제 입력을 보면 중복된 수가 허용된다.

우선 Node 클래스를 만들어 num입력값을 저장할 value변수와 입력값의 순서를 알려줄 index변수를 만들었다.
일정한 범위를 덱deque을 사용해 표현했다. 그리고 문제를 해결하기 위해 다음과 같은 조건을 만족시켰다.

1. 새로운 입력값 num이 들어올 때, 기존 deque에 있는 값들 중 num보다 큰 수는 제거했다. 범위 내의 최솟값을 구하기 때문에 num 보다 큰 수는 의미가 없기 때문이다. 그리고 num을 deque의 마지막에 추가하게 되면 deque는 자연스럽게 항상 정렬된 형태를 띤다.
2. 최솟값을 구할 때는 정렬된 deque의 첫 번째 값을 그대로 쓰면 된다. 단, 전 단계에서 우리는 D를 구하기 위한 범위를 특정하지 않았다. 그렇기에 첫 번째 값의 index가 범위의 시작을 알려주는 start값 보다 큰지 검사해 줘야 한다.
   

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        Deque<Node> deque = new LinkedList<Node>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            while (!deque.isEmpty() && deque.peekLast().value > num) {
                deque.pollLast();
            }
            deque.addLast(new Node(i, num));

            int start = i - L + 1;
            while (deque.peekFirst().index < start) {
                deque.pollFirst();
            }
            sb.append(deque.peekFirst().value).append(" ");
        }

        System.out.println(sb.toString());
    }
}

class Node {
    int index;
    int value;

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