내 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int win = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Deque<Integer> deque = new ArrayDeque<>();
        List<Integer> answer = new ArrayList<>();

        for(int i = 0; i < n; i++){
            if(!deque.isEmpty() && deque.peekFirst() <= i - win){
                deque.pollFirst();
            } // 윈도우 사이즈 제한

            while(!deque.isEmpty() && arr[deque.peekLast()] > arr[i]){
                deque.pollLast();
            }
            deque.addLast(i);
            answer.add(arr[deque.peekFirst()]);
        }

        StringBuilder sb = new StringBuilder();
        for(int val : answer){
            sb.append(val).append(" ");
        }
        System.out.println(sb.toString());

    }
}

설명

우선순위 큐를 써볼까 했다가 실패하였다.
결국 deque를 써야하는데 deque를 사용하다가도 deque의 중간에 있는 것까지 간섭하게 되면 시간초과가 발생하게 된다.
한참을 헤매다가 모노톤 큐라는 것을 사용해야 한다는것을 알게 되었다.

모노톤 큐

쉽게 생각해서 우선순위 큐의 Deque버전이다.
deque에 저장된 원소들이 정렬된 상태를 유지하도록 하는 특수한 형태의 deque이다.
보통 슬라이딩 윈도우에서 자주 사용된다고 한다...

일반적인 큐와는 다르게 값을 삽입시에 기존 deque의 뒤쪽 원소중에서 정렬상태를 깨버리는 원소는 제거하는 방식이다.

    for(int i = 0; i < n; i++){
        if(!deque.isEmpty() && deque.peekFirst() <= i - win){ //win은 입력값 L을 의미
            deque.pollFirst();
        } // 윈도우 사이즈 제한 목적

        while(!deque.isEmpty() && arr[deque.peekLast()] > arr[i]){
            deque.pollLast();
        } // 맨 마지막 요소가 삽입하고자 하는 값보다 크다면 -> 정렬이 깨짐 ex) 1 2 5 9 -> 1 2 5 9 6(정렬x)
        deque.addLast(i);
        answer.add(arr[deque.peekFirst()]);
    }

또한 모노톤 큐에는 인덱스를 넣는데한 모노톤 큐에는 인덱스를 넣는데 인덱스가 아닌 값을 집어넣게 된다면 정확한 값 비교가 어렵기 때문이다.

저작자표시 비영리 변경금지 (새창열림)