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

분류: 슬라이딩 윈도우, deque /

 

문제

문제 링크

문제 설명

N개의 수 A₁, A₂, ..., A_N과 L이 주어진다.

D_i = A_i-L+1 ~ A_i 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 A_i는 무시하고 D를 구해야 한다.

입력

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

둘째 줄에는 N개의 수 A_i가 주어진다. (-10⁹ ≤ A_i ≤ 10⁹)

출력

첫째 줄에 D_i를 공백으로 구분하여 순서대로 출력한다.

 

풀이

#include <iostream>
#include <deque>
using namespace std;

struct e {int idx, v;};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, L, x; cin >> N >> L;
    
    deque<e> dq;
    for(int i=0; i<N; i++){
        cin >> x;
        if(!dq.empty() && dq.front().idx == i - L)
            dq.pop_front();
        while(!dq.empty() && dq.back().v > x)
            dq.pop_back();
        dq.push_back({i, x});
        cout << dq.front().v << " ";
    }
}

`monotonic increasing deque`

인덱스 i-L 부터 i 까지 큐에 들어있다면 큐의 길이는 L+1이다.

따라서 for문에 진입했을 때 `front().idx`가 i-L이라면 `x`를 넣으면 큐의 길이는 L+1이 되므로 `pop_front`

deque는 monotonic increasing deque으로 `x`보다 큰 것들은 `pop_back`

`x` push 후 deque의 front는 `x`부터 뒤로 L만큼 구간의 최솟값이다.