11003번 최솟값 찾기

문제

https://www.acmicpc.net/problem/11003

접근 방식

✔️ Do it! 알고리즘 코딩 테스트 자바 편 풀이 참고

👉 슬라이딩 윈도우 + 덱 활용

정렬 효과를 내기 위해 덱을 활용한 점이 새로워서 기록한다 !

1 ≤ L ≤ N ≤ 5,000,000라는 조건으로 인해, 윈도우 사이즈가 5000000기 때문에 슬라이드 할 때마다 정렬을 수행할 순 없다. (정렬 시간: n O(log n), 요소 하나씩 이동 n => 총 시간 복잡도: n * n O(log n), n은 5000000까지)

정렬 문제를 해결하기 위해 스택 + 큐의 성질을 합쳐놓은 덱을 활용할 수 있다.

덱의 마지막 요소와 비교하여, 현재 값이 더 작은 경우 마지막 요소를 poll 함으로써 덱 내의 요소들을 오름차순으로 정렬하는 것이다. 그렇게 되면 맨 처음 요소가 최솟값이라는 사실이 보장되므로 첫번째 요소가 정답이 된다.

새로운 요소를 덱에 추가할 때, 처음 요소의 인덱스와 비교함으로써 윈도우 크기 validation을 수행하면 된다.

코드

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

public class Main {
    static class Node{
        long idx;
        int val;

        Node(long idx, int val){
            this.idx = idx;
            this.val = val;
        }
    }

    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());
        long n = Long.parseLong(st.nextToken());
        long l = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());

        Deque<Node> deque = new LinkedList<>();
        for (long i = 0; i < n; i++){
            int curVal = Integer.parseInt(st.nextToken());

            if (deque.isEmpty()) deque.addLast(new Node(i, curVal));
            else {
                // 맨 앞 인덱스 확인해서 윈도우만큼 poll
                if (i - deque.getFirst().idx >= l) deque.pollFirst();
                // 맨 뒤와 비교해가며 poll -> deque 정렬
                while (!deque.isEmpty() && deque.getLast().val > curVal) deque.pollLast();
                // 현재 값 추가
                deque.offerLast(new Node(i, curVal));
            }
            // 첫번째 값 == 최솟값 보장
            bw.write(deque.getFirst().val + " ");
        }
        bw.flush();
        bw.close();
    }
}