[백준] 11003번 - 최솟값 찾기 [Java][C++]

문제 링크

---

1. 문제 풀이

단조 덱을 활용한 슬라이딩 윈도우의 대표적인 문제로 인덱스를 저장하는 단조 덱을 활용하면 해결할 수 있다.

주어진 수열의 인덱스를 저장할 단조 덱을 선언한 후 수열을 순회하며 단조 덱의 맨 앞 원소가 구간의 최솟값인 인덱스가 되도록 유지했다. 슬라이딩 윈도우 과정에서 단조 덱의 최솟값 인덱스가 구간을 벗어나면 단조 덱에서 제거했고 새로 들어오는 인덱스는 단조성을 유지하는 위치에 넣어주며 불필요한 원소들을 제거하는 과정을 반복했다.

Java의 경우 약간 애매했지만 C++의 경우 그냥 우선순위 큐를 활용해도 넉넉하게 통과됐다.

---

2. 코드

1. 덱을 이용한 구간 최댓값 트릭 [Java]

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 단조 덱
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            // 구간에서 나가는 인덱스 처리
            if (!dq.isEmpty() && dq.peekFirst() == (i - L)) {
                dq.pollFirst();
            }

            // 구간으로 들어오는 인덱스 처리
            while (!dq.isEmpty() && arr[i] <= arr[dq.peekLast()]) {
                dq.pollLast();
            }

            dq.offerLast(i);

            sb.append(arr[dq.peekFirst()]).append(" ");
        }

        System.out.println(sb);
    }
}

2. 덱을 이용한 구간 최댓값 트릭 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, l;
    cin >> n >> l;

    vector<int> v(n);
    for (int& x : v) cin >> x;

    // 단조 덱
    deque<int> dq;
    for (int i = 0; i < n; i++) {
        // 구간에서 나가는 인덱스 처리
        if (!dq.empty() && dq.front() == (i - l)) {
            dq.pop_front();
        }

        // 구간으로 들어오는 인덱스 처리
        while (!dq.empty() && v[i] <= v[dq.back()]) {
            dq.pop_back();
        }

        dq.push_back(i);

        cout << v[dq.front()] << ' ';
    }
}

3. 우선순위 큐 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, l;
    cin >> n >> l;

    vector<int> v(n);
    for (int& x : v) cin >> x;

    // 우선순위 큐
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for (int i = 0; i < n; i++) {
        while (!pq.empty() && pq.top().second <= (i - l)) {
            pq.pop();
        }

        pq.push({v[i], i});

        cout << pq.top().first << ' ';
    }
}

---

3. 풀이 정보

1. 덱을 이용한 구간 최댓값 트릭 [Java]

언어	시간	메모리	코드 길이
Java 11	1888 ms	589912 KB	1186 B

2. 덱을 이용한 구간 최댓값 트릭 [C++]

언어	시간	메모리	코드 길이
C++ 17	1188 ms	42416 KB	635 B

3. 우선순위 큐 [C++]

언어	시간	메모리	코드 길이
C++ 17	1464 ms	119984 KB	505 B

---