[백준 11003] 최솟값 찾기 (Java) - 슬라이딩 윈도우 & 모노톤 덱 최적화

🚀 문제 핵심

• 데이터 규모: $N, L \le 5,000,000$ (매우 큼)
• 제한 조건: 시간 2.4초 / 메모리 512MB
• 목표: 모든 $i$에 대하여 $A_{i-L+1} \sim A_i$ 중 최솟값 찾기

---

💡 핵심 설계: 모노톤 덱 (Monotonic Deque)

단순 슬라이딩 윈도우로는 구간 내 최솟값을 $O(1)$에 찾을 수 없습니다. 우리는 덱(Deque)을 이용해 '최솟값이 될 가능성이 있는 후보'들만 오름차순으로 유지하는 전략을 사용합니다.

1. 윈도우 만료 제거 (Front): 덱의 맨 앞(peekFirst) 노드의 인덱스가 현재 범위를 벗어났다면(i - idx >= L) 제거합니다.
2. 무의미한 후보 제거 (Rear): 새로 들어올 값보다 큰 기존의 값들은 절대 최솟값이 될 수 없으므로 뒤에서부터 모두 제거합니다.
3. 최적화 포인트 (No Array): 500만 개의 데이터를 배열에 미리 담지 않고, 입력 스트림에서 읽는 즉시 덱에 넣어 공간 복잡도를 $O(L)$ 수준으로 유지했습니다.

---

💻 최종 최적화 코드 (Java)

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

public class Main {
    public static void main(String[] args) throws Exception {
        // 모노톤 덱 + 슬라이딩 윈도우 최적화 풀이
        try (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());
            StringBuilder sb = new StringBuilder();
            Deque<Node> dq = new ArrayDeque<>();

            for (int i = 0; i < N; i++) {
                // [Optimization] 배열을 쓰지 않고 바로 Node 객체 생성 및 처리
                int now = Integer.parseInt(st.nextToken());
                Node node = new Node(i, now);

                // 1. 윈도우 범위를 벗어난 인덱스 제거 (O(1))
                if (!dq.isEmpty() && i - dq.peekFirst().idx >= L) {
                    dq.pollFirst();
                }

                // 2. 현재 값보다 큰 이전 후보들 제거 (Monotonic Property 유지)
                // '나보다 크면서 나보다 먼저 들어온 애들'은 가차없이 삭제
                while (!dq.isEmpty() && dq.peekLast().val >= node.val) {
                    dq.pollLast();
                }

                dq.addLast(node);
                
                // 3. 덱의 맨 앞은 항상 현재 구간의 최솟값
                sb.append(dq.peekFirst().val).append(" ");
                
                // 중간 출력 최적화 (출력 버퍼 관리)
                if (i % 10000 == 0) {
                    bw.write(sb.toString());
                    sb.setLength(0);
                }
            }
            bw.write(sb.toString());
            bw.append("\n").flush();
        }
    }

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

---

🧐 기술적 통찰: 왜 배열을 안 쓰는 게 더 좋은가?

1. 메모리 절약: 5,000,000개의 int 배열은 약 20MB를 차지합니다. 배열 없이 처리하면 덱에 들어있는 최대 $L$개의 노드만 메모리에 유지하면 되므로 훨씬 효율적입니다.
2. Cache Locality: 데이터를 읽자마자 즉시 처리하므로 CPU 캐시 활용도가 높아져 성능 향상을 기대할 수 있습니다.
3. 가비지 컬렉션(GC) 부담 완화: 거대한 배열을 한 번에 할당하는 대신 필요한 만큼의 객체만 다룸으로써 메모리 관리 측면에서 이점을 가집니다.

---

🎯 마치며

이번 문제는 슬라이딩 윈도우와 단조 큐(Monotonic Queue)의 결합을 보여주는 정석적인 사례였습니다. 특히 대량의 데이터를 다룰 때는 알고리즘의 시간 복잡도($O(N)$)뿐만 아니라, 불필요한 자료구조 선언을 줄이는 공간 최적화 능력이 얼마나 중요한지 배울 수 있었습니다.