<Programmers> Heap_Double Priority Queue c++

queue에서 단순하게 최댓값과 최솟값만 구하면 되므로 min heap과 max heap 두 개를 만든다.
push는 각 queue에 해주고 max값을 pop할 경우 max heap에서, min값을 pop할 경우 min heap에서 pop을 해준다.

1. min heap, max heap 선언

priority_queue <int, vector<int>, greater<int>> pq_asc; //오름차순 (min heap)
priority_queue <int, vector<int>> pq_des; //내림차순 (max heap)

2. operation과 숫자가 들어갈 변수 선언

    string operation=op.substr(0,1);
    int num=stoi(op.substr(2));
    
    e.g. "I 5" 에서 operation에는 I, num에는 5가 저장
    

3. queue에 저장된 갯수가 0이면 각 queue를 초기화

    if (!cnt) {
        while (!pq_asc.empty()) pq_asc.pop();
        while (!pq_des.empty()) pq_des.pop();
    }
    

4. operation=="I" 이면 각 queue에 push

    if (operation=="I") {
        pq_asc.push(num);
        pq_des.push(num);
        cnt++;
    }
    

5. operation=="D"이고 num에 1이면 max pop, -1이면 min pop

    else {
        
        if (!cnt) continue;
        
        if (num==1) 
            pq_des.pop();
        else if (num==-1)
            pq_asc.pop();
        
        cnt--;
    }

전체 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
   
    priority_queue <int, vector<int>, greater<int>> pq_asc;
    priority_queue <int, vector<int>> pq_des;
   
    int cnt=0;
  
    for (string op : operations) {
      
        string operation=op.substr(0,1);
        int num=stoi(op.substr(2));
       
        if (!cnt) {
            while (!pq_asc.empty()) pq_asc.pop();
            while (!pq_des.empty()) pq_des.pop();
        }
       
        if (operation=="I") {
            pq_asc.push(num);
            pq_des.push(num);
            cnt++;
        }
       
        else {
           
            if (!cnt) continue;
           
            if (num==1) 
                pq_des.pop();
            else if (num==-1)
                pq_asc.pop();
           
            cnt--;
        }
    }
   
    if (cnt==0) {
        answer.push_back(0);
        answer.push_back(0);
    }
       
    else {
        answer.push_back(pq_des.top());
        answer.push_back(pq_asc.top());   
    }
   
    return answer;
}