[JAVA] 백준 11003 덱

 

 

11003번: 최솟값 찾기

문제

주어진 배열에서 A[i]의 이전 A[i-M+1] ~ A[i] 값들 중 최솟값을 정해서 출력하라.

풀이

덱을 사용해서 슬라이딩 윈도를 구현하였다.

1. 덱의 마지막부터 살펴보면서 자신보다 큰 값이 있다면 삭제한다.
2. 자신을 덱의 마지막에 추가한다.
3. 덱의 첫 번째가 index 범위를 벗어난다면 삭제한다.
4. 덱의 첫 번째 값이 최소값이므로 buffer writer에 추가한다.

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

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 M = Integer.parseInt(st.nextToken());

       Deque<Node> q = new LinkedList<>();

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++){
            int now = Integer.parseInt(st.nextToken());

            while(!q.isEmpty() && q.getLast().value > now){
                q.removeLast();
            }
            q.addLast(new Node(now, i));

            while(!q.isEmpty() && q.getFirst().index < i-M+1){
                q.removeFirst();
            }
            sb.append(q.getFirst().value).append(" ");
        }


        System.out.println(sb);
    }

        static class Node{
        int value;
        int index;

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

    }
    }
}

해결