[BaekJoon] 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 << ' ';
    }
}

---