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

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

min_heap, max_heap을 2개 관리하면서 숫자가 insert될 때마다 각 숫자의 index_count를 증가시켜주고, 이를 관리하기 위해 map을 사용한다. (map의 index_count가 의미하는 것은 현재 heap에 존재하는 key에 해당하는 숫자의 갯수이다)

그 후 Delete가 발생할 때에는 max_heap 혹은 min_heap에서 top을 pop해주고, map의 index_count를 감소시킨다. 추가적으로 map에서 내 숫자에 해당하는 index_count와 heap의 top이 갖는 index(insert시 부여되며, monotonic increase하는)가 일치할 때 까지 pop해준다.

코드를 보니 set을 이용하면 더 짧은 코드로 완성할 수 있는 것 같다.
set은 ordered이기 때문에 insert시 logN으로 insert를 해주기 때문에 heap과 시간복잡도가 똑같으며, iteratable하기 때문에 begin, end를 통해서 min값과 max값을 동시에 접근할 수 있다. 다음엔 set을 사용해봐야겠다.

코드는 아래와 같다.

#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;

#define pii pair<int, int>

map<int, int> m;
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    priority_queue<pii, vector<pii>, greater<pii>> min_pq;
    priority_queue<pii, vector<pii>> max_pq;
    
    for(auto it : operations) {
        if(it[0] == 'I') {
            string tmp(it.begin() + 2, it.end());
            int num = stoi(tmp);
            m[num]++;
            int idx = m[num];
            min_pq.push( {num, idx} );
            max_pq.push( {num, idx} );
        } else if(it[0] == 'D') {
            if(it[2] == '1') {
                while(1) {
                    if(max_pq.empty())
                        break;
                    pii pq_val = max_pq.top();
                    if(m[pq_val.first] != pq_val.second) {
                         max_pq.pop();
                    } else {
                        m[pq_val.first]--;
                        break;
                    }
                }
            } else {
                while(1) {
                    if(min_pq.empty())
                        break;
                    pii pq_val = min_pq.top();
                    if(m[pq_val.first] != pq_val.second) {
                         min_pq.pop();
                    } else {
                        m[pq_val.first]--;
                        break;
                    }
                }
            }
        }
    }
    
    int max_val = 0;
    int min_val = 0;
    while(1) {
        if(max_pq.empty())
            break;
        pii pq_val = max_pq.top(); max_pq.pop();
        if(pq_val.second > m[pq_val.first]) 
            continue;
        max_val = pq_val.first;
        break;
    }
    while(1) {
        if(min_pq.empty())
            break;
        pii pq_val = min_pq.top(); min_pq.pop();
        if(pq_val.second > m[pq_val.first]) 
            continue;
        min_val = pq_val.first;
        break;
    }
    answer.push_back(max_val);
    answer.push_back(min_val);
    
    return answer;
}