[백준][C++] 7662 우선순위 큐

프로그래머스에도 비슷한 문제가 있어서 그때는 파이썬으로 heapq 활용해서 간단하게 구현했었는데, 이번에는 C++로 풀었다. 파이썬에서 max(리스트) 기능이 얼마나 소중한거인지 깨달았다...

두개의 우선순위큐(min heap, max heap) 를 써야되는 것은 알고있었다. 그런데 시간초과가 문제였다.

처음에는 Delete할때마다 다른 큐에서도 pop하면서 찾아서 다시 넣어주고 그랬는데, 최악 케이스 N log(N)이라서 문제였나보다.

그래서 검색하던 도중 lazy update에 대해서 보게되었다. delete 해야할 것들을 따로 저장해주고, Delete때마다 pop()해서 나오는 힙에서 확인해주었다. qLen라는 것을 저장해두어 qLen이 0일때 발생하는 불필요한 동기화를 없애주었다.

// 반례 https://www.acmicpc.net/board/view/73633
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long int lli;
int T;
int k;
int qLen=0;
priority_queue<int,vector<int>,greater<int>> minq;
priority_queue<int,vector<int>,greater<int>> minqTobeDel;
priority_queue<int,vector<int>,less<int>> maxq;
priority_queue<int,vector<int>,less<int>> maxqTobeDel;
void Input(){
    cin >> k;
}
void removeMax(){
    int val = maxq.top();
    
    maxq.pop();
    minqTobeDel.push(val);
}
void removeMin(){
    int val = minq.top();
    minq.pop();
    maxqTobeDel.push(val);
}
void insertNum(int n){
    maxq.push(n);
    minq.push(n);
}
void clearQ(){
    priority_queue<int,vector<int>,greater<int>> minqEmpty;
    priority_queue<int,vector<int>,less<int>> maxqEmpty;
    priority_queue<int,vector<int>,greater<int>> lazyMinEmpty;
    priority_queue<int,vector<int>,less<int>> lazyMaxEmpty;

    maxq.swap(maxqEmpty);
    minq.swap(minqEmpty);
    maxqTobeDel.swap(lazyMaxEmpty);
    minqTobeDel.swap(lazyMinEmpty);
    qLen=0;
}
void lazyUpdateMaxq(){
    int val;
    int maxCandidate;
    while(!maxqTobeDel.empty()){
        val = maxqTobeDel.top();
        maxCandidate = maxq.top();
        if(val > maxCandidate){
            maxqTobeDel.pop();
        }else if(val < maxCandidate){
            return;
        }else {
            maxqTobeDel.pop(); 
            maxq.pop();
        }
    }
}
void lazyUpdateMinq(){
    int val;
    int minCandidate;
    while(!minqTobeDel.empty()){
        val = minqTobeDel.top();
        minCandidate = minq.top();
        if(val < minCandidate){
            minqTobeDel.pop();
        }else if(val > minCandidate){
            return;
        } else {
            minqTobeDel.pop();
            minq.pop();
        }
        
    }
}
void Solve(){
    char cmd;
    int n;
    for(int i=0; i<k; ++i){
        cin >> cmd >> n;
        //cout <<"=====" << cmd << " " << n << "\n";
        switch(cmd){
            case 'D':
                if(qLen > 0){
                    if(n == 1) {
                        lazyUpdateMaxq();
                        removeMax();
                        //lazyUpdateMinq();
                    }else if(n== -1) {
                        lazyUpdateMinq();
                        removeMin();
                        //lazyUpdateMaxq();
                    }
                    qLen--;
                }  // empty : pass
                break;
            case 'I':
                qLen++;
                insertNum(n);
                break;
        }
    }
    if(qLen ==0) cout << "EMPTY\n";
    else {
        lazyUpdateMaxq();
        lazyUpdateMinq();
        cout << maxq.top() <<" " << minq.top() << "\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> T;
    for(int i=0; i<T; ++i){
        clearQ();
        Input();
        //cout << "i : " << i << "\n";
        Solve();
    }
}

 

참고자료

https://kangwlgns.tistory.com/35

https://panty.run/pq-del-elem/

https://velog.io/@mttw2820/%EB%B0%B1%EC%A4%80-7662.-%EC%9D%B4%EC%A4%91-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90