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

silverCastle·2022년 5월 18일
0

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

✍️ 첫번째 접근

multimap을 사용하여 문제 번호와 난이도를 저장하는데 multimap은 자동으로 오름차순으로 정렬되기 때문에 pair<int,int> 꼴에서 첫번째에 난이도를, 두번째에 문제 번호를 저장하여 난이도 순으로 저장되게 하였다. "recommend", "add", "solved"는 문제대로 적용하면 되는데 여기서 주의할 점은 "recommend"에서 -1을 입력받았을 때 가장 어려운 문제의 번호를 출력해야 하는데 end() 함수는 마지막 원소의 그 다음을 가리키고 있기 때문에 --ma.end() 형태로 써야한다. 하지만 시간초과가 발생하게 되는데 아마 "solved"에서 시간초과가 발생하는 거 같다.

#include <bits/stdc++.h>
using namespace std;
int n, m;
multimap<int,int> ma;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    while(n--) {
        int p,l;
        cin >> p >> l;
        ma.insert(pair<int,int>(l,p));
    }
    cin >> m;
    while(m--) {
        string str;
        cin >> str;
        if(str.compare("add") == 0) {
            int p,l;
            cin >> p >> l;
            ma.insert(pair<int,int>(l,p));
        }
        else if(str.compare("recommend") == 0) {
            int num;
            cin >> num;
            if(num == 1) {
                cout << (*(--ma.end())).second << '\n';
            }
            else {
                cout << (*ma.begin()).second << '\n';
            }
        }
        else {
            int p;
            cin >> p;
            for(auto e: ma) {
                if(e.second == p) {
                    ma.erase(ma.find(e.first));
                    break;
                }
            }
        }
    }
    

    return 0;
}

✍️ 두번째 접근

"solved"에서 추천 문제 리스트에서 문제 번호 P를 제거하는 과정에서 시간 초과가 발생하는 거 같아서 multimap을 사용하는 대신 set type의 배열과 정수형 배열을 만들어 문제 번호와 난이도를 저장하였다. 이렇게 하여 문제를 해결하였는데 multimap과 set은 O(log n)으로 시간 복잡도는 동일한데 시간초과가 발생하지 않는 것으로 보아 "solved" 형태로 접근하는 방식이 있다면 set과 배열을 써서 해결해야함을 느꼈다.

#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[100005];
set<int> s[105];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    while(n--) {
        int p, l;
        cin >> p >> l;
        arr[p] = l;
        s[l].insert(p);
    }
    cin >> m;
    while(m--) {
        string str;
        cin >> str;
        if(str.compare("add") == 0) {
            int p,l;
            cin >> p >> l;
            arr[p] = l;
            s[l].insert(p);
        }
        else if(str.compare("recommend") == 0) {
            int x;
            cin >> x;
            if(x == 1) {
                for(int i = 100; i >= 1; i--) {
                    if(s[i].empty())
                        continue;
                    cout << *(--s[i].end()) << '\n';
                    break;
                }
            }
            else {
                for(int i = 1; i <= 100; i++) {
                    if(s[i].empty())
                        continue;
                    cout << *(s[i].begin()) << '\n';
                    break;
                }
            }
        }
        else {
            int p;
            cin >> p;
            s[arr[p]].erase(p);
            arr[p] = 0;            
        }
    }

    return 0;
}

0개의 댓글