BOJ 21939 문제 추천 시스템 Version 1

21939번:문제 추천 시스템 Version 1

문제 번호와 난이도로 구성된 데이터들의 Min, Max 값을 추출 또는 삽입, 삭제 쿼리를 처리하는 문제였다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define MAX 100001
using namespace std;

typedef pair<int, int> pii;
priority_queue<pii,vector<pii>,less<pii>> max_pq;
priority_queue<pii,vector<pii>,greater<pii>> min_pq;
int n, m;
int level[MAX];

void recommend(int flag){
    int p, l;
    if (flag == 1) {
        while(1){
            l = max_pq.top().first;
            p = max_pq.top().second;
            if(level[p]==l)
                break;
            max_pq.pop();
        }
		cout << p << '\n';
    } else {
		while(1){
			l = min_pq.top().first;
            p = min_pq.top().second;
            if(level[p]==l) break;
            min_pq.pop();
        }
    	cout << p << '\n';
	}
}

void add(int P,int L){
    level[P] = L;
    max_pq.push({L, P});
    min_pq.push({L, P});
}

void solved(int P){
    level[P] = 0;
}

void input(){
    cin >> n;
    int L, P;
    string cmd;
    while (n--) {
        cin >> P >> L;
        max_pq.push({L, P});
        min_pq.push({L, P});
        level[P] = L;
    }
    return;
}
void command(){
    int L, P, flag;
    string cmd;
    cin >> m;
    while(m--){
        cin >> cmd;
        if(cmd=="recommend"){
            cin >> flag;
            recommend(flag);
        }
        else if (cmd == "add") {
            cin >> P >> L;
            add(P, L);
        } else {
            cin >> P;
            solved(P);
        }
    }
    return;
}

void solution(){
    input();
    command();
    cout << '\n';
}

int main() {
    fastio;
    solution();
}

우선순위 큐자체는 minheap 이거나 maxheap 이기에 한 큐에서 min, max를 모두 O(1)로 뽑을 수 없다.

따라서 비교연산자를 less<>, greater<>로 각각 사용하는 우선순위 큐 2개를 사용한다.

큐에서 top을 뽑을 때는 level이라는 벡터를 난이도 기준으로 인덱스를 부여해 삭제 여부를 기억해놓는다.

level의 p 인덱스에는 난이도가 p인 문제의 번호 l이 들어있다. 이 때 0이면 없는 문제이다.

이를 통해 top을 뽑을 때 while문으로 level 벡터를 lookup하면서 해당 난이도의 문제 존재 여부를 체크하며, 존재할 때까지 뽑는다.

이 방법으로 두 큐의 동기화를 구현한다.