[백준] 11003 최솟값 찾기

문제 링크 : www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

문제 유형

Deque, 슬라이딩 윈도우

 

덱(Deque)을 사용해 구간 별 최솟값을 찾는 문제이다.

덱은 front와 back의 두 포인터를 가진 자료구조로, 삽입이 양방향으로 가능한 벡터라고 생각하면 편하다.

덱의 이러한 특징으로, 우리는 덱의 원소들을 특정 우선순위에 맞게 유지시킬 수 있다.

 

즉, 다음과 같은 과정을 통해 덱을 항상 오름차순으로 유지시킨다.

현재 가리키는 인덱스를 i라 할 때,

① 덱의 front 값이 (i - l + 1) 보다 작다면, 그 값을 pop 한다. 이는 덱의 크기가 최대 l이 되도록 유지시켜 준다.

② A[front]와 A[i]를 비교해, 더 작은 값을 출력한다. 이는 곧 D[i]의 값과 같다. 

③ A[back]의 값이 A[i]보다 작아질 때까지 덱의 back 값을 pop한다.

④ 인덱스 i의 값을 덱의 back에 push한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
 
#define INF 2100000000
 
using namespace std;
typedef pair<int, int> p;
 
int n, l, arr[5000000];
 
void get_answer() {
    deque<int> dq;
    dq.push_back(0);
    printf("%d ", arr[0]);
 
    for (int i = 1; i < n; i++) {
        int bound = i - l + 1 < 0 ? 0 : i - l + 1;
        while (!dq.empty()) {
            if (dq.front() < bound) dq.pop_front();
            else break;
        }
 
        //최솟값 출력
        if (dq.empty() || arr[i] < arr[dq.front()]) printf("%d ", arr[i]);
        else printf("%d ", arr[dq.front()]);
 
        while (!dq.empty()) {
            if (arr[dq.back()] > arr[i]) dq.pop_back();
            else break;
        }
 
        dq.push_back(i);
    }
    printf("\n");
}
 
void init() {
    cin >> n >> l;
    for (int i = 0; i < n; i++) cin >> arr[i];
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    get_answer();
 
    return 0;
}