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

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

프로그래머스

 

#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <sstream>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer={0,0};
    unordered_map<int,int> us;
    priority_queue<int> sa;// 내림
    priority_queue<int,vector<int>,greater<int>> sb;// 올림
    
    for(string& s : operations)
    {
        istringstream iss(s);
        string a,b;
        iss>>a;
        iss>>b;
        if(a[0]=='I')
        {
            int im = stoi(b);
            us[im]++;
            sa.push(im);
            sb.push(im);
        }
        else
        {
            if(us.empty())
                continue;
            if(b=="1")
            {
                while(!sa.empty()&&us.find(sa.top())==us.end())
                    sa.pop();
                us[sa.top()]--;
                if(us[sa.top()]==0)
                    us.erase(sa.top());
                sa.pop();
            }
            else
            {
                while(!sb.empty()&&us.find(sb.top())==us.end())
                    sb.pop();
                us[sb.top()]--;
                if(us[sb.top()]==0)
                    us.erase(sb.top());
                sb.pop();
            }
        }
    }
    while(!sa.empty()&&us.find(sa.top())==us.end())sa.pop();
    while(!sb.empty()&&us.find(sb.top())==us.end())sb.pop();
    if(!us.empty())
    {
        answer[0]=sa.top();
        answer[1]=sb.top();
    }
    return answer;
}

내림,올림차순의 우선순위큐를 두개 만들었다. 

unordered_map이라는 기준을 두고 이 map에 삽입된 유효한 원소들을 저장해둔다. 

그리고 각 내림 올림차순의 큐들에도 저장한다. 

만약 삭제입력이 들어왔을 때 현재 큐의 top이 유효한지를 map에 검색해서 파악한다. 

map에 없다면 이미 삭제된것이기에 빼고 다음을 확인한다. 

while(!sa.empty()&&us.find(sa.top())==us.end())
                    sa.pop();

이게 그 과정이다. 

 

하지만 이렇게 복잡하게 할 필요가 없었다. 

iterator를 이용해 하나의 큐에서 또는 map에서 map.begin() , --map.end() 를 사용하면 처음과 마지막원소를 알 수 있다는 것을 알게 되었다.