백준 21939번, 문제 추천 시스템 Version 1(C, C++)

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

    using namespace std;

    priority_queue<pair<int, int>> maxheap;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minheap;
    map<int, int> m;
    int main(){
        int N;
        int M;
        int L;
        int P;
        int command;
        cin>>N;
        for(int i = 0; i < N; i++){
            cin>>P>>L;
            m[P] = L;
            maxheap.push(make_pair(L, P));
            minheap.push(make_pair(L, P));
        }
        cin>>M;
        for(int i = 0; i < M; i++){
            string command;
            cin>>command;
            if(command == "recommend"){
                int x;
                cin>>x;
                if(x == 1){
                    while(maxheap.top().first != m[maxheap.top().second]){
                        maxheap.pop();  // 저장해둔 데이터와 우선순위에 저장된 데이터가 다른 경우, solved의 영향을 받은걸로 간주하고 pop()합니다.
                    }
                    cout<<maxheap.top().second<<'\n';
                }else{
                    while(minheap.top().first != m[minheap.top().second]){
                        minheap.pop();
                    }
                    cout<<minheap.top().second<<'\n';
                }
            }else if(command == "add"){
                int a; // 우선순위에 넣을려는 난이도
                int b; // 우선 순위에 넣을려는 문제 번호
                cin>>b>>a;
                maxheap.push(make_pair(a, b));
                minheap.push(make_pair(a, b));
                m[b] = a;
            }else if(command == "solved"){
                int x;
                cin >> x;
                m[x] = 0;
            }
        }   
        return 0;
    }

 

해당 문제는 최대힙의 구조를 갖는 우선순위 큐와 최소힙의 구조를 갖는 우선순위 큐를 이용한

이중우선순위 큐를 이용한 문제입니다.

문제에서 recommend 1 은 난이도가 같을 경우, 문제 번호가 큰 순서가 출력되도록 한다고 합니다.

최대힙의 구조를 갖는 우선순위 큐의 first가 같은 경우, 두번 째 second 값이 가장 큰 경우가 top에 위치하여 우선순위가 됩니다.

이와 같이 recommend -1은 난이도가 같을 경우, 문제 번호가 작은 순서대로 출력된다고 한다면

최소 힙의 first가 같은 경우, 두 번째 second 값이 가장 작은 경우가 top에 위치합니다.

 

그렇기 때문에 최대 힙의 구조를 갖는 우선순위 큐와 최소 힙의 구조를 갖는 우선순위 큐를 만들어야 합니다.

 

사실 이 문제는 문제 번호를 제거하는 solved를 어떻게 구현할 지가 문제입니다.

임의의 문제 번호를 우선순위 큐에서 제거해야 하는데,

 

처음에는 큐가 앞 뒤로 넣고 뺄 수 있기 때문에, 큐의 top을 push_back()하고 pop_front()하는 방식으로 임의의 문제번호가 나올 때까지 반복하여 해결하려고 했지만 해당 문제는 우선순위 큐이기 때문에 push_back()을 하였을 때, 우선 순위가 높은 경우 다시 재배치가 될 수 있기 때문에 이 방법은 쓸 수 없었습니다.

 

맵함수를 이용하여, 문제 번호와 난이도를 저장합니다.

그렇다면 우선순위 큐 top()의 정보와 맵함수의 정보가 같을 수 밖에 없습니다. 

solved가 입력 되었을 때, 위의 정보들이 다르게 만들어 주면 되겠습니다.

 

난이도가 1부터 10만까지 있습니다.

제거하려는 맵함수의 문제번호를 그대로 유지한 채, 난이도를 0으로 바꿔 준다면,

while문의 조건에서 맵의 저장된 난이도와 우선순위 큐에 저장된 난이도가 서로 다르다면 pop()을 합니다.