[백준] 7662번

priorty queue가 뭔지 대충 알게 됐다.

여기에 lazy deleted를 구분해야 하는지는 모르겠는데, 지금 코드상 분류해야 하는게 맞다.

이것 떄문에 4시간 넘게 걸렸다.

#include <iostream>
#include <optional>
#include <queue>
#include <unordered_map>


template <typename T>
class DoubleEndedQueue {
private:
    struct Compare {
        bool operator()(const T& a, const T& b) const {
            return a > b;
        }
    };
    std::priority_queue<T> maxHeap;
    std::priority_queue<T, std::vector<T>, Compare> minHeap;

    std::unordered_map<T, int> deletedMax;
    std::unordered_map<T, int> deletedMin;
    int actualSize = 0;

    void cleanMaxHeap() {
        while (!maxHeap.empty() && deletedMax[maxHeap.top()] > 0) {
            --deletedMax[maxHeap.top()];
            maxHeap.pop();
            // printMap();
        }
    }

    void cleanMinHeap() {
        while (!minHeap.empty() && deletedMin[minHeap.top()] > 0) {
            --deletedMin[minHeap.top()];
            minHeap.pop();
            // printMap();
        }
    }
public:
    // void printMap() {
    //     std::cout << "deleted: " << std::endl;
    //     for (int i = 0; i < deleted.size(); i++) {
    //         std::cout << i << " : " <<deleted[i] << "\n";
    //     }
    //     std::cout << std::endl;
    // }
    void enqueue(const T& item) {
        maxHeap.push(item);
        minHeap.push(item);
        actualSize++;
    }

    bool empty() const {
        return actualSize == 0;
    }

    std::optional<T> getMax(){
        if (empty()) return std::nullopt;
        cleanMaxHeap();
        return maxHeap.top();
    }

    std::optional<T> getMin() {
        if (empty()) return std::nullopt;
        cleanMinHeap();
        return minHeap.top();
    }

    std::optional<T> dequeueMax() {
        if (empty()) return std::nullopt;
        cleanMaxHeap();
        T value = maxHeap.top();
        deletedMin[value]++;
        maxHeap.pop();
        actualSize--;
        // printMap();
        return value;
    }

    std::optional<T> dequeueMin() {
        if (empty()) return std::nullopt;
        cleanMinHeap();
        T value = minHeap.top();
        deletedMax[value]++;
        minHeap.pop();
        actualSize--;
        // printMap();
        return value;
    }
};




int main() {
    int t;
    std::cin >> t;
    for (int i = 0; i < t; i++) {
        int k;
        std::cin >> k;
        DoubleEndedQueue<int> prioryQueue;
        char command;
        int value;
        for (int j = 0; j < k; j++) {
            std::cin >> command >> value;
            if (command == 'I') {
                prioryQueue.enqueue(value);
            } else if (command == 'D') {
                if (value == 1) {
                    auto _temp = prioryQueue.dequeueMax();
                    if (_temp != std::nullopt) {
                        // std::cout << "maxPop" << std::endl;
                        // std::cout << *_temp << std::endl;
                    }
                        // std::cout << prioryQueue.dequeueMax() << std::endl;
                } else if (value == -1) {
                    auto _temp = prioryQueue.dequeueMin();
                    if (_temp != std::nullopt) {
                        // std::cout << "minPop" << std::endl;
                        // std::cout << *_temp << std::endl;
                    }
                }
            }
        }

        if (prioryQueue.empty()) {
            std::cout << "EMPTY" << std::endl;
        } else {
            std::cout << *prioryQueue.getMax() << " " << *prioryQueue.getMin() << std::endl;
        }
    }

    return 0;
}