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

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

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

 

문제

N개의 추천 문제 리스트가 주어진다. 각각 문제번호 P와 난이도 L을 가지고 있다.

M개의 명령어가 주어진다.

• recommend x
  • x==1이면 난이도가 가장 높은 문제, 문제 번호가 가장 큰 수를 출력한다.
  • x==-1이면 난이도가 가장 낮은 문제, 문제 번호가 가장 작은 수를 출력한다.
• add P L
  • 문제번호가 P이고 난이도가 L인 문제를 추가한다.
• solved P
  • 문제번호 P를 리스트에서 삭제한다.

풀이

문제번호, 난이도가 주어지고

삽입과 삭제가 빈번하며 난이도의 최댓값, 최솟값도 구해야한다.

그냥 linear한 배열로 하면 삽입/삭제될 때마다 재정렬해주어야 하므로 시간이 굉장히 오래 걸린다.

 

삽입,삭제, 최대최솟값 모두 lgN인 set(이진탐색트리)를 이용하여 시간 안에 풀 수 있다.

 

문제 번호 <= 10^5, 문제 난이도 <=100으로 그리 크지 않다는 점을 이용해서 배열을 잡아준다.

 

주의할 점

set.begin()은 맨 처음 원소의 iterator를 가리키지만 set.end()는 맨 뒷 원소 다음 칸(빈 칸)의 iterator를 가리킨다. 

prev(set.end()) 나 --set.end()를 써줘야 한다.

 

전체 코드

/*boj g4 21939 문제 추천 시스템 Version 1*/
#include <iostream>
#include <set>
#define MAXN 100005
using namespace std;

int N, M;
int probLevel[MAXN];     // probLevel[문제번호] = 난이도
set<int> levelProb[102]; // levelProb[난이도] = 문제번호 set
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int p, l;
        cin >> p >> l;

        if (probLevel[p] != 0) {
            levelProb[probLevel[p]].erase(p);
        }

        probLevel[p] = l;
        levelProb[l].insert(p);
    }
    cin >> M;

    string command;
    while (M--) {
        int x, P, L;
        cin >> command;
        if (command == "recommend") {
            cin >> x;
            if (x == 1) { // 가장 어렵고 문제 번호가 큰 문제
                for (int i = 100; i >= 0; i--) {
                    if (levelProb[i].empty()) continue;

                    cout << *(--levelProb[i].end()) << "\n";
                    break;
                }
            } else { // x == -1
                for (int i = 1; i <= 100; i++) {
                    if (levelProb[i].empty()) continue;

                    cout << *(levelProb[i].begin()) << "\n";
                    break;
                }
            }
        } else if (command == "add") {
            cin >> P >> L;

            if (probLevel[P] != 0) {
                levelProb[probLevel[P]].erase(P);
            }

            probLevel[P] = L;
            levelProb[L].insert(P);
        } else if (command == "solved") {
            cin >> P;
            levelProb[probLevel[P]].erase(P);
            probLevel[P] = 0;
        }
    }
}