백준 21939 문제 추천 시스템 Version 1 혼내주기

 

난이도가 100까지 밖에 없는 점을 이용해서 100개의 오름차순 우선순위 큐와 내림차순 우선순위 큐를 만든다.

add: 오름/내림 차순 우큐에 값을 넣고 해당 문제 번호의 난이도를 기록한다.
solved: 해당 문제 번호의 난이도를 초기화한다.
recommend: 1인 경우, 높은 난이도 우큐부터 뒤지면서 유효한 문제 번호를 찾는다. 유요하지 않은 경우는 기록된 난이도의 값이 0으로 초기화 되어있거나 해당 난이도와 (아래 코드의 경우 j) 기록된 난이도가 다른 경우이다.

 

풀이를 좀 더 꼼꼼하게 생각하자... 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

priority_queue<int> maxHeap[105];
priority_queue<int, vector<int>, greater<int>> minHeap[105];
int level[100005];
int n, m;

void input() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        int a, b; cin >> a >> b;
        maxHeap[b].push(a);
        minHeap[b].push(a);
        level[a] = b;
    }
    cin >> m;
    
}

int main() {
    fastio;
    input();

    for(int i = 0; i < m; ++i) {
        string a; int b, c; 
        cin >> a >> b;
        
        if(a == "add") {
            cin >> c;
            maxHeap[c].push(b);
            minHeap[c].push(b);
            level[b] = c;
        }
        
        else if(a == "recommend") {
            // print hardest #question
            if(b == 1) {
                for(int j = 100; j >= 1; --j) {
                    if(maxHeap[j].empty()) continue;
                    while(!maxHeap[j].empty() && (!level[maxHeap[j].top()] || level[maxHeap[j].top()] != j)) {
                        maxHeap[j].pop();
                    }

                    if(!maxHeap[j].empty()) {
                        cout << maxHeap[j].top() << "\n";
                        break;
                    }
                }
            }
            // print easiest #question
            else {
                for(int j = 1; j <= 100; ++j) {
                    if(minHeap[j].empty()) continue;
                    while(!minHeap[j].empty() && (!level[minHeap[j].top()] || level[minHeap[j].top()] != j)) {
                        minHeap[j].pop();
                    }

                    if(!minHeap[j].empty()) {
                        cout << minHeap[j].top() << "\n";
                        break;
                    }
                }
            }
        }
        // solved
        else {
            level[b] = 0;
        }
    }
    
    return 0;
}