[Algorithm] 프로그래머스 C++ : 이중우선순위큐

 

 

https://programmers.co.kr/learn/courses/30/lessons/42628#

코딩테스트 연습 - 이중우선순위큐

 

이중우선순위큐는 그냥 두개의 우선순위큐를 오름차순, 내림차순으로 만들고 가상으로 관리한다.

 

두개를 똑같이 관리하면서 이중우선순위큐에 몇개의 원소가 남았는지 cnt에 저장해놓는다.

(가상의 이중우선순위큐가 비어도 두개의 큐는 그냥 우선순위큐라서 비지 않으니까)

 

"D 1"일 땐 최댓값 내림차순 우선순위큐에서 pop하고 cnt를 1 감소시키고

"D -1"일 땐 최솟값 오름차순 우선순위큐에서 pop하고 cnt를 1 감소시킨다.

 

 

 

 

Code

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer(2);
    priority_queue<int, vector<int>, greater<int>> pq_asc;
    priority_queue<int, vector<int>> pq_des;
    int cnt = 0;
    
    for(string op : operations) {
        // 큐가 비었으면 싹 초기화
        if(!cnt) {
            while(!pq_asc.empty()) pq_asc.pop();
            while(!pq_des.empty()) pq_des.pop();
        }
        
        // 삽입
        if(op[0] == 'I') {
            pq_des.push(stoi(op.substr(2)));
            pq_asc.push(stoi(op.substr(2)));
            cnt++;
        }
        // 삭제
        else {
            // 빈 큐에 데이터를 삭제하라는 연산일 경우 무시
            if(!cnt) continue;
            
            // 최댓값 삭제
            if(op[2] == '1') {
                pq_des.pop();
                cnt--;
            }
            // 최솟값 삭제
            else {
                pq_asc.pop();
                cnt--;
            }
        }
        
    }
    
    if(cnt) {
        answer[0] = pq_des.top();
        answer[1] = pq_asc.top();
    }
    
    return answer;
}