백준) 11003 최소값 찾기

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

정수 배열에 대해, 각 인덱스로 자신이 부분수열의 끝이고 길이가 L인 부분수열을 만들 수 있다.

각 부분수열의 최소값을 구해야 한다. (정수 배열의 길이 <= 오백만)

처음엔 세그먼트 트리 풀이만 생각이 났다. 근데 오백만이라 nlogn만 해도 오억이라 시간안에 풀 수 없었다.

복잡한 세그먼트 트리로만 헤매고 있었던 이유는,

각 부분수열의 최소값을 구할 때, 전 인덱스로 구한 최소값을 활용하는게 어려웠기 때문이다.

최소값이 부분수열의 맨 처음에 있었다면, 이번에 최소값을 구할 땐, 이전의 최소값은 구간에 포함이 안되고 새로 구해야 했다.

이러한 최악의 경우는 계속 일어날 수 있고(오름차순 정렬된 배열이라면), 좋은 풀이가 아니었다.

결국 이렇게 최악의 경우에서, 다음으로 작은 최소값을 알고 있으면 해결할 수 있다.

이 최소값도 다시 구간에서 벗어날 수 있으므로, 최소값들 후보를 죄다 갖고 있으면 된다!

이러한 자료구조를 고민하다가 덱을 쓰기로 했다.

덱의 맨 앞은 최소값을 가지고, 뒤로 갈수록 다음 최소값 후보들이 이어진다.

따라서 덱의 front에선 최소값들을 활용하고, 뒤로는 최소값 후보들을 집어넣으면 된다.

작업후에는 L-i ~ i 까지 최소값들 후보들이 덱에 들어가 있을 것이다.

#include <stdio.h>
#include <deque>
#include <algorithm>
using namespace std;
 
int n, l, a;
deque<pair<int, int>> dq;
 
int main() {
    scanf("%d %d", &n, &l);
    for (int i = 0; i < n; ++i) {
        while (dq.size() && dq.front().second <= i - l)
            dq.pop_front();
 
        scanf("%d", &a);
        while (dq.size() && dq.back().first >= a)
            dq.pop_back();
 
        dq.push_back({ a,i });
        printf("%d ", dq.front().first);
    }
    return 0;
}