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

우선순위 큐 문제

www.acmicpc.net/problem/7662

 

programmers.co.kr/learn/courses/30/lessons/42628

해당 문제와 동일합니다.

---

[문제 풀이]

 

kangwlgns.tistory.com/35

 

---

[소스 코드]

 

C++ / 이중 우선순위 큐 구현

#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <sstream>
#include <iostream>

using namespace std;
typedef long long ll;

template <typename T>
class dual_priority_queue {
    priority_queue<T> maxq;
    priority_queue<T, vector<T>, greater<T>> minq;
    unordered_map<T, int> maxdel, mindel;

public:
    dual_priority_queue() {}

    void push(T data) {
        maxq.push(data);
        minq.push(data);
    }

    void popMax() {
        T data = maxq.top();
        maxq.pop();

        if (!mindel.insert(make_pair(data, 1)).second) {
            ++mindel[data];
        }

        synchronize();
    }

    void popMin() {
        T data = minq.top();
        minq.pop();

        if (!maxdel.insert(make_pair(data, 1)).second) {
            ++maxdel[data];
        }

        synchronize();
    }

    bool empty() {
        return maxq.empty() || minq.empty();
    }

    T topMax() {
        return maxq.top();
    }

    T topMin() {
        return minq.top();
    }

    void synchronize() {
        while (!minq.empty()) {
            T cur = minq.top();
            if (mindel.find(cur) == mindel.end()) break;
            if (--mindel[cur] == 0) mindel.erase(cur);
            minq.pop();
        }

        while (!maxq.empty()) {
            T cur = maxq.top();
            if (maxdel.find(cur) == maxdel.end()) break;
            if (--maxdel[cur] == 0) maxdel.erase(cur);
            maxq.pop();
        }
    }
};


int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int T; cin >> T;
    while (T--) {
        dual_priority_queue<ll> dpq;
        int N; cin >> N;
        while (N--) {
            string command; ll number;
            cin >> command >> number;

            if (command == "I") {
                dpq.push(number);
            }
            else {
                if (dpq.empty()) continue;

                if (number == 1) dpq.popMax();
                else dpq.popMin();
            }
        }

        if (dpq.empty()) cout << "EMPTY\n";
        else cout << dpq.topMax() << ' ' << dpq.topMin() << '\n';
    }

    return 0;
}

 

Java / TreeMap이용

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            TreeMap<Integer, Integer> map = new TreeMap<>();

            int N = Integer.parseInt(br.readLine());
            while (N-- > 0) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                
                char c = st.nextToken().charAt(0);
                int n = Integer.parseInt(st.nextToken());

                if (c == 'I') {
                    if (map.containsKey(n)) map.replace(n, map.get(n) + 1);
                    else map.put(n, 1);
                } else {
                    if (map.isEmpty()) continue;

                    if (n == 1) {
                        int key = map.lastKey();
                        if (map.get(key) == 1) map.remove(key);
                        else map.replace(key, map.get(key) - 1);
                    } else {
                        int key = map.firstKey();
                        if (map.get(key) == 1) map.remove(key);
                        else map.replace(key, map.get(key) - 1);
                    }
                }
            }

            if (map.isEmpty()) sb.append("EMPTY");
            else sb.append(map.lastKey()).append(' ').append(map.firstKey());
            sb.append('\n');
        }

        System.out.println(sb.toString());
        br.close();
    }

}