[BOJ 11003] 최솟값 찾기

문제 출처 : https://www.acmicpc.net/problem/11003

 

풀이 :

 

슬라이딩 윈도우로 푸는 문제이고 덱으로 풀었습니다.

값을 받아서 덱의 맨 뒤에서 자신보다 큰 수를 다 팝한후 푸쉬합니다.

그 이유는 현재 윈도우에서 현재값보다 큰 수들은 최솟값 후보가 될 수 없기 때문입니다.

최솟값을 출력할 때에는 현재 덱의 맨 앞의 값이 윈도우에 포함되는지 여부를 파악한 후 포함되지 않으면 최솟값이 아니니 팝하고 포함되면 출력합니다.

 

#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;
 
struct num {
    int v, s;
    num(int v, int s) :v(v), s(s) {}
    num(){}
};
 
int n, l, t;
 
deque<num> dq;
 
int main() {
    scanf("%d %d", &n, &l);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        while (dq.size() && dq.back().v >= t)dq.pop_back();
        dq.push_back(num(t, i));
        if (dq.front().s < i - l + 1)dq.pop_front();
        printf("%d ", dq.front().v);
    }
}