[BOJ] 21939번 : 문제 추천 시스템 Version 1 C++ 풀이

우선순위 큐 두개로 해결할 수 있는 문제이다.
recommend 명령어가 1인지, -1인지에 따라 큰 값부터, 작은 값부터 찾아야 하는 값이 달라진다. 그래서 최대 힙과 최소 힙을 함께 사용하면 된다는 것을 눈치챌 수 있다.

그리고 별도의 방문 배열을 만들어서 각 문제가 solved 된 적이 있는지 확인하기로 하자. 그러면 최대힙에 있는 문제가 해결되었을때, 최소힙에서 이를 판별할 수 있게 된다. 구현이 조금 귀찮았던 문제다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 2000000000
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int N, M, pos[NUM];
bool visited[NUM];

struct st {
    int p, l, idx;
};

struct compare1 {
	bool operator()(const st s1, const st s2) {
        if (s1.l == s2.l) {
            return s1.p < s2.p;
        }
        return s1.l < s2.l;
	}
};

struct compare2 {
	bool operator()(const st s1, const st s2) {
        if (s1.l == s2.l) {
            return s1.p > s2.p;
        } 
        return s1.l > s2.l;
	}
};


priority_queue<st, vector<st>, compare1> pq1;
priority_queue<st, vector<st>, compare2> pq2;


void init() {
    memset(visited, false, sizeof(visited));
    memset(pos, 0, sizeof(pos));
    cin >> N;
    for (int i=1; i<=N; i++) {
        st s;
        cin >> s.p >> s.l;
        visited[i] = true;
        pos[s.p] = i;
        s.idx = i;
        pq1.push(s);
        pq2.push(s);
    }
    

    cin >> M;

    for (int i=1; i<=M; i++) {
        string s;
        int x, y;
        cin >> s;
        if (s == "add") {
            cin >> x >> y;
            st ss;
            ss.p = x;
            ss.l = y;
            ss.idx = N+i;
            pq1.push(ss);
            pq2.push(ss);
            visited[N+i] = true;
            pos[ss.p] = N+i;
        }
        if (s == "recommend") {
            cin >> x;
            if (x == 1) {
                while (true) {
                    auto t = pq1.top();
                    if (visited[t.idx]) {
                        cout << t.p << '\n';
                        break;
                    } 
                    pq1.pop();
                }
            } else {
                while (true) {
                    auto t = pq2.top();
                    if (visited[t.idx]) {
                        cout << t.p << '\n';
                        break;
                    } 
                    pq2.pop();
                }
            }
        }
        if (s == "solved") {
            cin >> x;
            int idx = pos[x];
            visited[idx] = false;
        }
    }
}       

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