[프로그래머스] level.3 - 이중우선순위큐(C++)

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

내 해답

문제에 적힌 그대로 우선 순위 큐를 두 개 두어 이 문제를 해결할 수 있다.

우선 순위 큐 중 하나는 내림차순 우선 순위 큐로 최댓값을 삭제하기 위한 용도로 사용한다.

또 다른 하나는 오름차순 우선 순위 큐로 최솟값을 삭제하기 위한 용도로 사용한다.

 

숫자가 추가되면 두 큐에 숫자를 추가한다.

최댓값 삭제 시, 내림차순 우선 순위 큐에서 숫자를 삭제하고,

최솟값 삭제 시, 오름차순 우선 순위 큐에서 숫자를 삭제하면 된다.

 

여기서 중요한 점은 숫자의 개수를 카운팅해야 한다는 것이다.

두 큐 중 하나에서만 값을 삭제하기 때문에 모든 숫자가 삭제 되어도 큐에는 여전히 값이 남아있다.

그러므로 숫자의 개수를 카운팅하다가 숫자 카운트가 0이 되면 모든 큐를 비워야 한다.

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer(2, 0);
    priority_queue<int, vector<int>> pq_max;          
    priority_queue<int, vector<int>,greater<int>>pq_min;
    int num_count = 0;
    
    for(const auto& s : operations)
    {
        int data = stoi(s.substr(2));
        
        // num_count가 0이 되면 큐들을 비운다 
        if(!num_count)
        {
            pq_max = priority_queue<int, vector<int>>();
            pq_min = priority_queue<int, vector<int>, greater<int>>(); 
        }
        
        // 숫자 삽입
         if(s[0] == 'I')
         {
             pq_max.push(data);
             pq_min.push(data);
             ++num_count;
         }
        else
        {
            if(!num_count)
                continue;
            
            // 최댓값 삭제
            if(1 == data)
                pq_max.pop();

            // 최솟값 삭제
            else
                pq_min.pop();
            
            --num_count;
        }
    }
    
    if(num_count > 0)
    {
        answer[0] = pq_max.top();
        answer[1] = pq_min.top();
    }
    
    
    return answer;
}