백준 11003 최솟값 찾기 혼내주기

 

슬라이딩 윈도우 + pq/deque 문제.
내가 푼 방법은 우선순위 큐에 값과 인덱스를 넣어서 매번 범위에서 벗어난 최솟값을 비우고 유효한 최솟값을 출력하는 방식이었다. 근데 다른 사람들의 풀이를 보니 덱을 이용하면 최대 사이즈를 l개로 유지하면서도 풀 수 있길래 바꿔보았다. 확실히 pq는 범위에서 벗어난 얘들이 큐에 남아서 메모리를 많이 차지하는 반면 덱은 메모리를 반밖에 사용하지 않는다.

 

생각해보니 pq로 풀면 슬라이딩 윈도우라고 하기도 뭐한 것 같다...

 

 

 

비교 - 아래가 우선순위 큐를 이용한 풀이, 위가 덱을 이용한 풀이

 

덱

#include <iostream>
#include <deque>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, l, num; cin >> n >> l;
    deque<pair<int, int> > dq;  //value, idx
    for(int i = 0; i < n; ++i) {
        cin >> num;
        while(!dq.empty() && dq.front().second < i-l+1)
            dq.pop_front();
        while(!dq.empty() && dq.back().first >= num)
            dq.pop_back();
        dq.push_back({num, i});
        cout << dq.front().first << " ";
    }
}

 

우선순위 큐

#include <iostream>
#include <queue>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, l, num; cin >> n >> l;
    priority_queue<pair<int, int> > pq; //value, idx
    for(int i = 0; i < n; ++i) {
        cin >> num;
        pq.push({-num, i});
        if(i >= l){
            while(pq.top().second < i-l+1)
                pq.pop();
        }
        cout << -pq.top().first << " ";
    }
}