[BOJ_C++] 11003번: 최솟값 찾기

CODE

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, l;
    deque<pair<int, int>> dq;
    
    cin >> n >> l;
    vector<int> v(n);
    for(int i=0; i<n; i++){
        cin >> v[i];
    }

    for(int i=0; i<n; i++){
        if(!dq.empty() && dq.front().second <= i-l) dq.pop_front();
        while(!dq.empty() && dq.back().first > v[i]) dq.pop_back();
        dq.push_back(make_pair(v[i], i));
        cout << dq.front().first << " ";
    }

    return 0;
}

문제 풀이

1. 크기가 n인 벡터에 값을 입력 받는다.
2. dq 원소의 값과 인덱스가 pair가 되어 저장되고 이때 원소의 값이 오름차순이 되도록 관리해야 한다.
   1. 만약 dq가 비어있지 않고, dq의 제일 앞 원소의 인덱스가 i - l의 크기보다 작거나 같다면 dq의 크기를 l로 유지하기 위해 범위를 벗어나는 제일 앞 원소를 제거한다.
   2. 만약 dq가 비어있지 않고, dq의 제일 뒤 원소의 값이 현재 맨 뒤에 삽입하려는 값보다 크면 배열을 최솟값으로 유지하기 위해 맨 위 원소가 현재 원소보다 작아질 때까지 원소를 제거한다.
3. dq의 맨 뒤에 현재 원소의 값과 인덱스 값을 넣는다.
4. dq의 맨 앞에 값을 출력한다.

결과