[백준] 문제 추천 시스템 Version 1 #21939

설명

maxHeap과, minHeap을 두 개 동시에 관리하면서 푸는 문제.
두 개의 Heap의 sync를 맞춰야 해서 arr을 체크용으로 두고, 삭제되었는지를 판단해서 계산

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int arr[100001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    priority_queue<pair<int, int>> maxHeap;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    int N; cin >> N;
    for (int i=0; i<N; i++) {
        int P, L;
        cin >> P >> L;
        maxHeap.push({ L, P });
        minHeap.push({ L, P });
        arr[P] = L;
    }
    int M; cin >> M;
    for (int i=0; i<M; i++) {
        string cmd; int n1, n2;
        cin >> cmd; cin >> n1;
        if (cmd == "add") {
            cin >> n2;
            arr[n1] = n2;
            maxHeap.push({ n2, n1 });
            minHeap.push({ n2, n1 });
        }
        else if (cmd == "recommend") {
            if (n1 == 1) {
                while(maxHeap.top().first != arr[maxHeap.top().second]) maxHeap.pop();
                cout << maxHeap.top().second << '\n';
            }
            else if (n1 == -1) {
                while(minHeap.top().first != arr[minHeap.top().second]) minHeap.pop();
                cout << minHeap.top().second << '\n';
            }
        }
        else if (cmd == "solved") {
            arr[n1] = 0;
        }
    }

    return 0;
}