[백준 11003] 최솟값 찾기 (슬라이딩 윈도우)

 

풀이

슬라이딩 윈도우를 덱으로 구현하여 정렬할 수 있다.

처음 인덱스부터 덱에 넣어가면서 만약 들어온 새로운 값이 덱의 마지막 인덱스와 비교했을때 

덱의 마지막인덱스의 값 > 덱에 새로 들어온 값일 경우 마지막 인덱스의 값을 삭제한다.

또한 예시처럼 L을 3처럼 잡고할 경우 인덱스가 3을 넘어가버리면 처음 인덱스는 제거해줘야한다.

똑같은 방식으로 계속 해가면 된다.

 

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

public class Main {
    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> mydeque = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            int now = Integer.parseInt(st.nextToken());

            while (!mydeque.isEmpty() && mydeque.getLast().value > now) {
                mydeque.removeLast();
            }
            mydeque.addLast(new Node(now,i));
            if (mydeque.getFirst().index <= i - L) {
                mydeque.removeFirst();
            }
            bw.write(mydeque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }

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

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