1. 문제

📌 문제 보러 가기!

2. 접근법

• deque 자료구조를 사용하여 정렬을 구현한다.
• (index, value) 쌍의 Node 오브젝트를 생성한다.
• deque의 끝에서부터 비교하여 더 큰 값들은 모두 삭제한다.
• Node 오브젝트를 가장 끝에 삽입한다.
• deque의 앞에서부터 비교하여 인덱스가 벗어난 값들은 모두 삭제한다.
• 가장 앞에 있는 것이 최솟값이다.

3. 코드

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class BaekJoon11003 {
    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 생성
        Deque<Node> myDeque = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            int t = Integer.parseInt(st.nextToken());
            // deque에 값이 존재하고, 가장 끝의 값이 t(현재 값)보다 크다면 마지막 값을 삭제한다.
            while (!myDeque.isEmpty() && myDeque.getLast().num > t) {
                myDeque.removeLast();
            }
            // Node Object를 deque에 삽입
            myDeque.add(new Node(i, t));
			// deque에 값이 존재하고, 가장 앞의 값이 index를 벗어났다면 가장 앞의 값을 삭제한다.
            while (!myDeque.isEmpty() && myDeque.getFirst().index <= i - L) {
                myDeque.removeFirst();
            }
            // 가장 앞의 값이 최솟값이다.
            bw.write(myDeque.getFirst().num + " ");
        }
        bw.flush();
        bw.close();
    }

    static class Node {
        public int index;
        public int num;

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