[ 백준 / C++ ] 11003 : 최솟값 찾기

[ 문제 ]

 

11003번: 최솟값 찾기 (acmicpc.net)

 

[ 접근방법 ]

 

C++ STL deque을 활용한다.

 

deque에 { value, index } 데이터를 넣고, 이를 통해 D를 결정할 것이다.

 

수를 입력받고 deque 뒤에 넣기 때문에, deque 안의 데이터들은 index만 봤을 때 오름차순으로 저장되어 있다.

따라서 가장 앞 데이터 index가 l 범위에서 벗어났는지만을 체크하면 된다.

 

또한, deque에 원소를 넣기 전에 뒤 데이터 value가 입력받은 수보다 작은지 체크해준다.

현재 deque에 들어있는 데이터들이 포함되어 계산된 모든 D는 현재 입력받은 데이터도 포함하여 계산한다.

따라서 미리 value를 비교하여 trash data를 제거해주는 작업을 진행한다.

 

단순히 deque의 push, pop 연산만을 사용하였기에 O(n)에 충분히 해결 가능하다.

 

[ 소스코드 ]

 

#include <iostream>
#include <deque>

using namespace std;

int n, l, a;
deque<pair<int, int>> dq;

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

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

    return 0;
}