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

프로그래머스

 

• 각각 내림차순, 오름차순으로 값을 저장하는 우선순위 큐 2개를 활용
• 삽입은 두 큐에 동시에 수행하고 최댓값 삭제는 내림차순 큐에서 최솟값 삭제는 오름차순 큐에서 수행
• 추가로 삽입을 수행한 횟수와 삭제를 수행한 횟수가 같아지면 두 큐를 모두 비워줘야함 

 

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

using namespace std;

// 우선순위큐 2개를 생성해서 하나는 내림차순, 하나는 오름차순으로 정렬
// 삽입 같은 경우에는 두 큐에 모두 수행
// 최댓값은 내림차순, 최솟값은 오름차순 큐에서 수행
// 이후 하나가 비어있으면 나머지 하나도 비어있는 것이므로 [0, 0] 리턴
// 아니라면 각각 front() 값을 리턴하면 됨

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int> lesser_pq;
    priority_queue<int, vector<int>, greater<int>> greater_pq;
    int cnt = 0;
    
    for(int i = 0; i < operations.size(); i++) {
        if(operations[i] == "D 1") {
            if(!lesser_pq.empty()) {
                lesser_pq.pop();
                cnt--;
            }
        }
        else if(operations[i] == "D -1") {
            if(!greater_pq.empty()) {
                greater_pq.pop();
                cnt--;
            }
        }
        else {
            string str = "";
            istringstream iss(operations[i]);
            
            iss >> str >> str;
            
            lesser_pq.push(stoi(str));
            greater_pq.push(stoi(str));
            
            cnt++;
        }
        
        if(cnt == 0) {
            while(!lesser_pq.empty()) lesser_pq.pop();
            while(!greater_pq.empty()) greater_pq.pop();
        }
    }
    
    if(lesser_pq.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(lesser_pq.top());
        answer.push_back(greater_pq.top());
    }
    
    return answer;
}