11003. 최솟값 찾기

11003. 최솟값 찾기

 

 

우선순위 큐를 활용한 슬라이딩 윈도우 문제이다.

 

최소힙을 유지하는 우선순위 큐를 구성하고, 인덱스와 값을 넣는다.

 

매번 top에서 원소를 확인할 때, 유효 기간이 지난(인덱스를 벗어나는) 원소를 pop한 후 출력하면 된다.

• 현재 원소보다 큰 유효기간이 지난 원소는 어차피 효력이 없으므로 문제되지 않는다.

 

#include <iostream>
#include <queue>

using namespace std;

struct Elem
{
    int idx;
    int data;

    friend bool operator < (const Elem& A, const Elem& B) { return A.data > B.data; }
};

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, L;
    priority_queue<Elem> prQue;

    cin >> N >> L;

    for (int i = 0; i < N; ++i)
    {
        int data;

        cin >> data;
        prQue.push({i, data});

        while (prQue.top().idx <= i - L)
            prQue.pop();

        cout << prQue.top().data << " ";
    }

    return 0;
}