핵심! 최솟값 찾기 (슬라이딩 윈도우 + 덱)

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

11003번: 최솟값 찾기

N개의 수 A1, A2, ..., AN과 L이 주어진다.

di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.

이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

 

윈도우의 크기는 최솟값을 구하는 범위가

i - L + 1부터 i까지이므로 'L'

최솟값을 구하기 위해 정렬을 한다면

일반적으로 정렬은 O(nlogn)이므로

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

인 범위에서는 시간 초과가 날 게 뻔하다.

 

그러므로, O(n)의 시간 복잡도로 해결을 해야겠다.

deque을 이용해서 정렬하기

#include <iostream>
#include <deque>
using namespace std;
 
// first는 값, second는 index
typedef pair<int, int> Node;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, l;
    cin >> n >> l;
    deque<Node> d;
 
    // 시간 복잡도 O(N)으로 간다
    for (int i = 0; i < n; i++)
    {
        int now;
        cin >> now;
 
        // 값이 들어올 때마다 정렬하지 않고
        // 현재 수보다 큰 값을 덱에서 제거
        while (d.size() && d.back().first > now)
        {
            d.pop_back();
        }
        d.push_back(Node(now, i));
 
        // 슬라이딩 윈도우의 범위를 벗어나면 덱에서 제거
        //pop_front()로!
        if (d.front().second <= i - l)
        {
            d.pop_front();
        }
        
        //범위의 최소값은 deque의 제일 앞 
        cout << d.front().first << ' ';
    }
}