백준 7662 - 이중 우선순위 큐 [C/C++]

7662번: 이중 우선순위 큐 (acmicpc.net)

이중 우선순위 큐 문제 설명

 

문제 입력과 출력 형식

 

 이번 문제를 통해 개인적으로 새롭게 접했던 Priority Queue 객체를 써볼 수 있는 좋은 경험이었다. 

 

 우선 필자는 우선순위 큐를 떠올리기 전 간단히 sorting 하면 되지 않을까라고 생각했었는데, insert instruction이 들어올 때만 정렬을 한다고 하더라도 매번 정렬하는 것은 매번 비효율적이며, 극단적인 케이스의 경우 백만 번 동안 sorting을 해야 하니 시간 초과가 날 것은 분명했다.

 

 구글링을 하다 보니 C++에는 우선 순위 큐 라는 객체가 있다는 것을 알게 되었고, 이번 기회에 잘 써먹어보자라고 생각하여 공부 후 코드에 적용하였다.

 

추후 우선 순위 큐와 Heap과 관련된 내용을 포스팅 후 링크를 걸어놓겠다.

 

수정 ) [자료구조] Heap이란? — 예비 대학원생의 Computer Science 저장소 (tistory.com)

 

아래는 위 문제를 해결하기 위한 코드이다.

 

우선 값이 큰 순서 대로 자동 정렬되는 우선 수위 큐와, 작은 순서 대로 자동 정렬되는 우선 순위 큐 2개를 선언한다.

 

D -1이 뜬다면 minHeap에서, D 1이 뜬다면 maxHeap에서 빼낸다. 이 때, 반대 쪽 큐에서 빠진 원소가 아직 이 쪽 큐에서 빠지지 않은 경우가 생길 수 있으므로, 애초에 insert 될 때 어떤 원소가 몇 번 들어가 있는지 체크를 해주어야 한다.

 

이 때 주의할 점은, 배열이 아닌 "map"을 사용하여 저장해야 한다는 것이다. 어떤 수가 들어올 지 모르는 상황에 배열 21억개의 index를 가진 채로 선언하는 것은 메모리 부분에서도 매우 비효율적이기 때문이다.

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>

using namespace std;
int testcase, howmany, how;
long long int icnt = 0;
string what;
priority_queue<long long int, vector<long long int>, greater<long long int>> minpq;
priority_queue<long long int> maxpq;
map<long long int, long long int> mp;

void cleanqueues() {
    while(!minpq.empty() && mp[minpq.top()]==0){minpq.pop();}
    while(!maxpq.empty() && mp[maxpq.top()]==0){maxpq.pop();}
}

void deletemin() {
    if (!minpq.empty()){
        mp[minpq.top()]--;
        minpq.pop();
    }
}

void deletemax() {
    if (!maxpq.empty()){
        mp[maxpq.top()]--;
        maxpq.pop();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> testcase;
    while(testcase>0){
        testcase--;
        cin >> howmany;
        while(!minpq.empty()){minpq.pop();}
        while(!maxpq.empty()){maxpq.pop();}
        mp.clear();
        while(howmany>0){
            howmany--;
            cin >> what >> how;
            if(what=="I"){
                icnt++;
                maxpq.push(how);
                minpq.push(how);
                if(mp.find(how)!=mp.end()){mp[how]++;}
                else{mp[how]=1;}
            }
            else{
                icnt = (icnt>0 ? icnt-1 : 0);
                if(how==-1 && !minpq.empty()){
                    cleanqueues();
                    deletemin();
                }
                else if (how==1 && !maxpq.empty()){
                    cleanqueues();
                    deletemax();
                }
            }
        }
        cleanqueues();
        if(icnt==0 || maxpq.empty() || minpq.empty() || minpq.top() > maxpq.top()){
            cout << "EMPTY" << '\n';
        }
        else{
            cout << maxpq.top() << " " << minpq.top() << '\n';
        }
    }
    return 0;
}