[백준 7662번] [Multiset] 이중 우선순위 큐

Approach

이 문제를 보고 파블로프의 개처럼 최댓값과 최솟값을 다루는 문제이므로 우선순위 큐를 생각할 수 있으나 잘 생각해보면 비효율적이라는 것을 쉽게 알 수 있다.

 

우선순위 큐를 활용한 접근 방법의 가장 큰 문제점은 최대힙과 최소힙이 서로 동기화가 안된다는 것이다. 즉 최대힙을 통해 지운 데이터가 최소합에 반영되기가 힘들다. 이 문제점을 해결하기 위해서 Map이나 Set 등의 자료구조등을 활용해서 지운 데이터인지를 계속해서 비교하는 방법등을 활용할 수 있으나 비효율적이다.

 

잘 생각해보면 Multiset은 order가 이미 힙트리 상에 저장되어있다. 즉, 이를 활용해주면 하나의 자료구조로 두 개의 값을 동시에 다룰 수 있는 장점이 있다.

Codes

Priority_queue를 활용한 방법

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    int t;
    cin >> t;
    while(t--){
        int k;
        priority_queue<int> max_store;
        priority_queue<int, vector<int>, greater<int> > min_store;
        multiset<int> set_store;
        cin >> k;
        for(int i = 0; i < k; i++){
            char l;
            int n;
            cin >> l >> n;
            if(l == 'D'){
                // 최대 삭제
                if(n == 1){
                    while(!max_store.empty()){
                        int check = max_store.top();
                        if(set_store.find(check) != set_store.end()){
                            max_store.pop();
                            set_store.erase(set_store.find(check));
                            break;
                        }
                        max_store.pop();
                    }
                }
                else{      
                    while(!min_store.empty()){
                        int check = min_store.top();
                        if(set_store.find(check) != set_store.end()){
                            min_store.pop();
                            set_store.erase(set_store.find(check));
                            break;
                        }
                        min_store.pop();
                    }       
                }
            }
            else{
                max_store.push(n);
                min_store.push(n);
                set_store.insert(n);
            }
        }
        if(set_store.empty()){
            cout << "EMPTY\n";
        }
        else{
            cout << *(--set_store.end()) << " " << *set_store.begin() << "\n";
        }
    }
    return 0;
}

Multiset를 활용한 방법

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    int t;
    cin >> t;
    while(t--){
        int k;
        multiset<int> s;
        cin >> k;
        for(int i = 0; i < k; i++){
            char l;
            int n;
            cin >> l >> n;
            if(l == 'D'){
                if(s.empty()) continue; // Exception handling
                if(n == 1) s.erase(--s.end());
                else s.erase(s.begin());
            }
            else s.insert(n);
        }
             
        if(s.empty()){
            cout << "EMPTY\n";
        }
        else{
            cout << *(--s.end()) << " " << *s.begin() << "\n";
        }
    }
    return 0;
}