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

시간 복잡도가 1초이고, 입력값이 10만개, query 의 값이 만개 이므로 각 query 마다 log(N) 의 복잡도 내로 답이 나오도록 처리해야 문제가 풀리게 된다.

이를 위해 입력 시에만 Nlog(N) 의 복잡도가 걸리고 query 에 따른 값을 뽑아 낼 때는 log(N) 의 복잡도를 가지는 min heap, max heap 2개와 solved 된 문제를 체킹하기 위한 배열 1개가 잇으면 간단히 풀리게 된다.

단, solved 된 문제를 체킹할 때 해당 문제의 난이도를 배열에 저장함으로써 이 후 top 의 값이 체킹해두었던 난이도가 아니라면 pop 하고 다음 수를 보는 로직을 통해 문제를 해결할 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int n, a, b;
string tp;
int check[100001];
priority_queue<pii, vector<pii>, greater<pii>> minQ;
priority_queue<pii, vector<pii>> maxQ;

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        maxQ.push({ b, a });
        minQ.push({ b, a });
        check[a] = b;
    }

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tp;
        if (tp == "add") {
            cin >> a >> b;
            maxQ.push({ b, a });
            minQ.push({ b, a });
            check[a] = b;
        }
        else if (tp == "recommend") {
            cin >> a;
            if (a == 1) {
                while (check[maxQ.top().second] != maxQ.top().first) {
                    maxQ.pop();
                }
                cout << maxQ.top().second << endl;
            }
            else if (a == -1) {
                while (check[minQ.top().second] != minQ.top().first) {
                    minQ.pop();
                }
                cout << minQ.top().second << endl;
            }
        }
        else if (tp == "solved") {
            cin >> a;
            check[a] = -1;
        }
    }
    return 0;
}

 

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

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