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

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

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

코드

 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int> maxHeap, minDeleteHeap;
priority_queue<int, vector<int>, greater<int>> minHeap, maxDeleteHeap;
 
vector<int> solution(vector<string> operations) {
    for (auto& iter: operations) {
        if (iter[0] == 'I') {
            string s(iter.begin() + 2, iter.end());
            maxHeap.push(stoi(s));
            minHeap.push(stoi(s));
        }
        else {
            if (iter[2] == '1') {
                if (!maxHeap.empty()) {
                    minDeleteHeap.push(maxHeap.top());
                    maxHeap.pop();
                }
            }
            else {
                if (!minHeap.empty()) {
                    maxDeleteHeap.push(minHeap.top());
                    minHeap.pop();
                }
            }
            while (!maxDeleteHeap.empty() and maxDeleteHeap.top() == maxHeap.top()) {
                maxDeleteHeap.pop();
                maxHeap.pop();
               }
               while (!minDeleteHeap.empty() and minDeleteHeap.top() == minHeap.top()) {
                minDeleteHeap.pop();
                minHeap.pop();
               }
           }
    }
    if (maxHeap.empty() and minHeap.empty()) return {0, 0};
    else return {maxHeap.top(), minHeap.top()};
}

 

---

풀이

이중 우선순위 큐를 구현하기 위하여 여러 개의 우선순위 큐를 사용한다는 아이디어를 떠올릴 수 있다면 풀 수 있는 문제입니다.

 

출처: 프로그래머스

 

 

maxHeap	16	-5643
minHeap	-5643	16

주어진 인풋에서 앞의 2가지만 실행한다면, 힙에 다음과 같이 저장될 것입니다.

 

maxHeap	16	-5644
minHeap	16

 그 다음 D -1 을 실행한다면 힙이 다음과 같이 변형될 것입니다.

그렇지만 maxHeap에서 pop을 하면 16이 빠져버리기에 변형시킬 수 없습니다.

 

maxDeleteHeap	-5643
minDeleteHeap

이를 해결하기 위하여 삭제할 값을 기억하는 다른 힙을 생성해 줍니다. 

max(min)DeleteHeap은 이후 삭제할 값을 기억해두었다가, 또 D를 호출한다면 각 Heap에서 데이터를 삭제해 줍니다.