[Algorithm] 7662: PriorityQueue

• toc {:toc}

📦7662: PriorityQueue

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-05
문제 확인하기

풀이

• priority_queue를 사용해서 풀이했다.
• max, min 우선순위 큐를 만든다.
• push할 때는 모두 min, max 모두에 push한다.
• pop할 때 -1일 때는 min, 1일 때는 max에서 pop한다. 이때 각각 pop하지 않은 큐(1일 때는 min, -1일 대는 max)에서는 여전히 값이 남아 있을 수 있다. 이를 체크하고 제거해준다.

#include <iostream>
#include <queue>
#include <map>
#define endl '\n'
using namespace std;
 
priority_queue<int> max_q;
priority_queue<int, vector<int>, greater<int>> min_q;
map<int, int> ckpt;
 
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T, k, val;
    char ch;
 
    cin >> T;
 
    while(T--){
        while(!max_q.empty()) max_q.pop();
        while(!min_q.empty()) min_q.pop();
        ckpt.clear();
        cin >> k;
        while(k--){
            cin >> ch >> val;
 
            if (ch=='I'){
                max_q.push(val);
                min_q.push(val);
                ckpt[val]++;
            }
            else{
                if (val==1){
                    if (!max_q.empty()){
                        ckpt[max_q.top()]--;
                        max_q.pop();
                    }
                }
                else{
                    if (!min_q.empty()){
                        ckpt[min_q.top()]--;
                        min_q.pop();
                    }
                }
                while(!min_q.empty() && ckpt[min_q.top()]==0)
                    min_q.pop();
                while(!max_q.empty() && ckpt[max_q.top()]==0)
                    max_q.pop();
            }
        }
        if (max_q.empty() || min_q.empty()) {
            cout << "EMPTY" << endl;
        }
        else{
            cout << max_q.top() << ' ' << min_q.top() << endl;
        }
    }
 
    return 0;
}