백준[11003] 최솟값 찾기

문제 설명

문제 링크

http://icpc.me/11003

11003번: 최솟값 찾기

풀이

덱을 이용하여 풀 수 있다.

덱에 들어있는 값을 단조적으로 유지하면서 k번째 값이 들어올 때 그 k번째 값이 덱에서 가장 큰 값을 유지하게 덱을 관리하면 된다.

또한 덱에는 k - l - 1 이후에 들어온 값만 있어야 한다.

덱을 위와 같이 관리하면 덱의 제일 앞에 있는 값이 최솟값이 되게 된다.

cf) 세그먼트 트리를 이용하면 O(nlogn)에 풀 수 있을 것 같지만 상수 때문인지 시간 초과가 난다. 덱을 이용한 풀이가 정해여서 시간제한을 세그 트리로 뚫지 못하게 만든 거 같다.

코드

#include <cstdio>
#include <deque>

using namespace std;

int main() {
    int n, l; scanf("%d %d", &n, &l);
    deque<pair<int, int>> dq;
    for (int i = 0; i < n; i++) {
        int inp; scanf("%d", &inp);
        while (!dq.empty() && dq.front().second <= i - l) dq.pop_front();
        while (!dq.empty() && dq.back().first > inp) dq.pop_back();
        dq.push_back({inp, i});
        printf("%d ", dq.front().first);
    }
}