[Java] 11003번. 최솟값 찾기 (#덱)

1. 문항출처 : https://www.acmicpc.net/problem/11003

2. 자바의 자료구조(Deque)

자바의 자료구조를 나타내는 대표적인 인터페이스로 Map, Collection이 있다.

이번 문제에서 사용할 Deque은 Collection, List, Deque 인터페이스를 상속하는
LinkedList 구현체이다.
배열의 처음과 끝에서 입출력이 가능하다는 특징을 가지고 있는 자료구조이다.

3. 문제해석

첫번째 줄에 N개의 수를 나타내는 N값과 부분구간의 길이 L이 주어지고
두번째 줄에 공백을 기준으로 구분된 N개의 수가 주어진다.
N개의 수에서 i번째 숫자를 기준으로 i번째 수를 포함하여 앞쪽으로 L개의 숫자 구간 내에서 최솟값을 출력한다.
예제입력에서 1 5 2 3 6 2 3 7 3 5 2 6 이 N개의 수로, 부분구간의 길이가 3으로 주어져있는데
첫번째 수인 1은 첫번째 수를 포함하여 앞 구간이 없으므로 1이 최솟값이고
두번째 수인 5는 본인을 포함한 앞 구간이 1 5 이므로 1이 최솟값,
세번째 수인 2는 본인을 포함한 앞 구간이 1 5 2 이므로 1이 최솟값,
네번째 수인 3은 본인을 포함한 앞 구간이 5 2 3 이므로 2가 최솟값,
다섯번째 수인 6은 본인을 포함한 앞 구간이 2 3 6 이므로 2가 최솟값.. 이런 형태로
최솟값들을 나열하면 1 1 1 2 2 ... 형태로 출력해야하므로
예제출력 정답은 1 1 1 2 2 2 2 2 3 3 2 2 가 된다.

4. 해결전략

문제가 간단하므로 생략하겠다.

5. 해결코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
    static class Node {
        private int index;
        private int num;

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

    static Deque<Node> deque = new LinkedList<>();
    static StringBuilder sb = new StringBuilder();
    static int N, L;

    public static void main(String[] args) throws IOException {
        StringTokenizer 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++) {
            addNode(i, Integer.parseInt(st.nextToken()));
        }
        System.out.println(sb);

    }

    static void addNode(int index, int num) {
        while (!deque.isEmpty() && deque.getLast().num > num) {
            deque.removeLast();
        }
        deque.addLast(new Node(index, num));
        while (deque.getFirst().index <= index - L) {
            deque.removeFirst();
        }
        sb.append(deque.getFirst().num).append(" ");
    }

}