[힙] 이중우선순위큐

프로그래머스

 

 

우선 순위 큐를 이용해서 주어진 연산을 하는 문제

연산은 더하기 빼기가 있으며, 덧셈은 경우 없이 더해주면 되고, 뺄셈의 경우 최댓값을 빼는 경우와 최솟값을 빼는 경우를 생각해주면 된다. 최댓값을 꺼낼 때와 최솟값을 꺼낼 때 이중 우선순위 두 개를 사용해서 연산을 해주면 되는데,

 

이때 최댓값을 빼는 경우(pop) 최솟값은 빼지 않기 때문에 이미 pop한 숫자를 다시 한번 pop할 경우가 있다. 따라서 이 경우 몇 개의 숫자가 남아 있는지 count를 해주어야 한다.

빼기 연산을 할 때 카운트가 0만 아니라면 뺄 수 있다 위 그림을 보듯 양방향으로 가기 때문에 남아 있는 숫자가 있는 한 겹칠 일이 없기 때문이다.

 

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer(2);
    
    int cnt = 0;
    
    priority_queue<int, vector<int>> max_pq;
    priority_queue<int, vector<int>, greater<int>> min_pq;
    
    for(string operation : operations){
        if(cnt == 0){
            while(!max_pq.empty()) max_pq.pop();
            while(!min_pq.empty()) min_pq.pop();
        }
        
        if(operation[0] == 'I'){
            int n = stoi(operation.substr(2));
            max_pq.push(n);
            min_pq.push(n);
            cnt++;
        } else{
            if(cnt == 0) continue;
            
            if(operation[2] == '1'){
                max_pq.pop();
                cnt--;
            } else{
                min_pq.pop();
                cnt--;
            }
        }   
    }
    
    if(cnt != 0){
        answer[0] = max_pq.top();
        answer[1] = min_pq.top();
    }
    
    
    return answer;
}