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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42628 

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

 

 

풀이

그대로 구현하면 돼서 간단한 문제이지만 한 가지 문제가 있다.

min heap과 max heap을 각각 선언하여 각각의 최솟값 최댓값을 pop하는 방식으로 구현했을 때

 

각 힙에 3을 넣고, -3을 넣은 뒤 최솟값 pop 최댓값 pop을 하게 되면

maxHeap에는 -3이 남아있을 것이고 minHeap에는 3이 남아있을 것이다.

하지만 원래는 모든 힙에는 원소가 없어야한다.

 

이를 방지하기 위해 카운트 변수를 생성하여 원소에 삽입할 때에는 증가, 삭제할 때에는 감소시켜준다.

따라서, 카운트가 0일 때에는 모든 큐가 비워지도록 한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int, vector<int>, greater<> > minHeap;
    priority_queue<int> maxHeap;
    int cnt = 0; //원소의 개수
    
    for(int i=0; i<operations.size(); i++){
        if(cnt == 0){
            while(!maxHeap.empty()) maxHeap.pop();
            while(!minHeap.empty()) minHeap.pop();
        }
        
        if(operations[i][0] == 'I') {
            int tmp = stoi(operations[i].substr(2));
            minHeap.push(tmp);
            maxHeap.push(tmp);
            cnt++;
        }
        else {
            if(cnt == 0) continue;
            
            if(operations[i][2] == '1'){
                maxHeap.pop();
                cnt--;
            }
            else {
                minHeap.pop();
                cnt--;
            }
        }
    }
    
    if(cnt == 0){
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(maxHeap.top());
        answer.push_back(minHeap.top());
    }
    
    return answer;
}