이중 우선순위 큐 (feat. 백준, 7662번)

이중 우선순위 큐
https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <set>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N;
    string str;
    cin >> N;
    for(register int n = 0, v; n < N; ++n){
        cin >> v;
        multiset<int> q;
        for(register int i = 0, x; i < v; ++i){
            cin >> str;
            cin >> x;
            if(!str.compare("D")){
                if(!q.empty()){
                    if(x == -1)
                        q.erase(q.begin());
                    else
                        q.erase(--q.end());
                }
            }
            else{
                q.insert(x);
            }
        }
        if(q.empty())
            cout << "EMPTY\n";
        else
            cout << *(--q.end()) << " " << *(q.begin()) << "\n";
    }
    return 0;
}
// *&)*@*

 

반응형

 

1. 정렬과 앞뒤의 삽입, 삭제가 이루어져야 합니다.
2. deque 자료구조를 사용하면 가장 좋겠지만 매번 정렬할 순 없으므로 set을 사용하였습니다.
3. map은 key-value 구조인데 반해 multiset은 key만 갖는 구조이므로 map보다 삽입, 삭제 속도면에서 유리합니다.