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

https://www.acmicpc.net/problem/21939

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

#include <iostream>
#include <queue>
#include <map>

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> lpq;     //{난이도, 문제 번호}, 최댓값
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> gpq;     //{난이도, 문제 번호}, 최솟값



int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n;

    map<int, bool> isExist;      //문제 번호, 있는지 여부


    for (int i = 0; i < n; i++) {

        int p, l;
        cin >> p >> l;

        lpq.push(make_pair(l, p));
        gpq.push(make_pair(l, p));
        isExist[p] = true;


    }

    cin >> m;

    for (int i = 0; i < m; i++) {
        string opt;

        cin >> opt;


//        x가 1인 경우 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력한다.
//                만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다.
//        x가 -1인 경우 추천 문제 리스트에서 가장 쉬운 문제의 번호를 출력한다.
//                만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다.
        if (opt.compare("recommend") == 0) {
            int x;
            cin >> x;

            switch(x) {
                case 1:
                    cout << lpq.top().second << "\n";
                    break;
                case -1:
                    cout << gpq.top().second << "\n";
                    break;

            }
        }
        //추천 문제 리스트에 난이도가 L인 문제 번호 P를 추가한다. (추천 문제 리스트에 없는 문제 번호
        //P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)
        else if (opt.compare("add") == 0) {
            int p, l;
            cin >> p >> l;

            lpq.push(make_pair(l, p));
            gpq.push(make_pair(l, p));
            isExist[p] = true;


        }

/*        추천 문제 리스트에서 문제 번호
        P를 제거한다. (추천 문제 리스트에 있는 문제 번호
        P만 입력으로 주어진다.)*/
        else if (opt.compare("solved") == 0) {
            int p;
            cin >> p;
            isExist[p] = false;

            //삭제 값이 top에 남아있지 않도록 처리
            while (!gpq.empty() && isExist[gpq.top().second] == false) {
                gpq.pop();
            }
            while (!lpq.empty() && isExist[lpq.top().second] == false) {
                lpq.pop();
            }

        }
    }



    return 0;
}

 

recommend 옵션에서 x에 따라 최댓값, 최솟값을 출력해야 하므로 이중 우선순위 큐의 응용문제이다.

우선순위 큐에는 {난이도, 문제번호} 순으로 pair를 넣어 난이도 순, 난이도가 같을 경우 문제번호 순으로 정렬되도록 한다.

map<문제 번호, 존재 여부> 로 해당 문제의 존재 유무를 확인한다. 

 

1. recommend: 주어진 x에 따라 최댓값, 최솟값을 우선순위 큐의 top을 참조하여 출력한다.

2. add: 처음 문제 리스트 입력과 똑같이 구현한다.

3. solved: 이걸 구현하는 게 핵심이었다고 생각한다. 주어진 문제를 제거한다. 해당 문제의 존재 여부를 false로 만든다. 이후 lpq, gpq에 해당 문제가 top으로 되어있다면 recommend 연산에서 이미 지워진 문제가 출력될 수 있으므로 각 큐의 top에 해당 문제가 존재하지 않는다면 pop하여 top의 문제를 제거한다.

 이렇게 하면 만약 각 큐의 top이 아닌 문제를 제거하더라도 해당 문제 앞의 값이 모두 지워진다면 이 연산에서 해당 문제도 지워지게 된다.