[C++] 백준/BOJ - 21939 : 문제 추천 시스템 Version 1

---

문제 이해 단계

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

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

문제가 N개 주어지는데, (문제의 번호, 난이도)의 쌍으로 이루어진다.

해당 조건일 때 recommend x로 나오는 출력을 그대로 구현해라는 문제

 

---

문제 접근 단계

문제 제한 사항부터 살펴보자.

문제의 개수 N은 최대 100,000개까지, 명령어 M의 개수는 10,000개이다.

최대 100,000개까지의 모든 탐색을 다한다고 해도
10^5 * 10^4 = 10^9으로 int형을 넘어가지 않기 때문에 안전하다.

해당 문제에서 고려해야 할 점은 입출력이 너무 많다는 것이다.

알고리즘에서는 입출력이 가장 많은 시간을 잡아먹는다.
그런데 해당 문제는 그 입출력이 너무 많다.

그렇기 때문에 시간초과가 나기 쉽기 때문에
최적화가 정말 중요한 문제라고 할 수 있다.

 

시간이 오래 걸리는 작업

그렇다면 시간이 오래 걸리는 작업은 무엇이 있을까?

일단 "add" 명령어는 기존 문제 리스트에 추가를 해주는 것이다.

따라서 처음 입력받는 것과 똑같이 해주면 되기 때문에 시간이 오래 걸리는 작업은 아니다.

"recommend"를 살펴보자. 딱 봐도 시간이 오래 걸릴 것이다.

가지고 있는 문제 중에 최댓값과 최솟값을 찾아야 하기 때문에
매번 전체 정보의 탐색이 들어가야 한다.

물론 최솟값, 최댓값 탐색은 오름차순/내림차순 정렬을 통해 최적화가 가능하다.

하지만 문제는 "add"를 통해 새로운 문제 정보가 들어오면
정렬이 깨지기 때문에 또 정렬을 해줘야 한다.

즉 언제 발생할지 모르는 add 때문에, recommend 명령어가 들어올 때마다 정렬을 매번 해줘야 한다.
이것은 매번 문제 전체를 훑는 것만큼이나 시간 소모가 크다.

그래서 사용한 것이 set이라는 자료 구조이다.

set은 이진탐색트리 구조로 내부적으로 자동으로 오름차순 또는 내림차순 정렬을 한다.
정렬을 하는 데 걸리는 시간은 O(logN) 밖에 걸리지 않는다.(엄청나게 빠르다.)

그래서 전체적으로 문제의 정보는
set 자료구조를 사용하여 난이도를 기준으로 오름차순 정렬한다.

마지막으로 "solved"를 따져보는데, 여기서는 리스트에서 문제 번호를 통해서 제거한다. 
즉, 들어오는 정보가 문제 번호밖에 없다는 뜻이다.

문제 정보는 중복되지 않기 때문에 리스트를 탐색해서,
맞는 것이 있다면 set에서 제거하면 되긴 한다.

그런데 그렇게 되면 또 전체 리스트에서 찾는 과정을
반복해야 하기 때문에 시간이 오래 걸린다.

그래서 문제 번호를 알고 있다면 바로 난이도를 알도록 하여
set.erase가 가능하도록 map을 사용하도록 한다.

map을 사용하여 map [문제 번호] = 해당 문제 난이도를 구한다.

이후 set.erase(해당 문제 난이도, 문제번호)를 통해 문제 리스트에서 삭제한다.

전체적인 로직은 위와 같다.
이제 문제 구현 단계에서 자세한 로직을 살펴보자.

 

 

---

문제 구현 단계

#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

using namespace std;

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    set<pair<int,int>> s;
    map<int,int> m;

    int N,M;
    cin >> N;
    for(int i = 0; i < N; i++){
        int problem, level;
        cin >> problem >> level;
        // 난이도 기준으로 오름차순 정렬하기 위해 난이도를 앞으로
        s.insert({level,problem});
        m[problem] = level;
    }

    cin >> M;

    while(M--){
        string input;
        cin >> input;

        if(input == "recommend"){
            int order;
            cin >> order;
            if(order == 1) {
                auto it = s.rbegin(); // set 맨 뒤에 있는 문제
                cout << it -> second << "\n";
            }
            else{
                auto it = s.begin(); // 가장 앞에 있는 문제
                cout << it -> second << "\n";
            }
        }
        else if(input == "add"){
            int problem,level;
            cin >> problem >> level;
            s.insert({level,problem});
            m[problem] = level;
        }
        else{
            int problem;
            cin >> problem;
            // 문제 번호를 키로 난이도를 구함
            s.erase({m[problem],problem});
        }
    }
}

set은 정렬 기준을 세워주지 않으면 기본적으로 오름차순 정렬을 한다.

또한 set의 내부에 pair을 가지면, first값을 기준으로 오름차순 하기 때문에
난이도 기준으로 정렬하기 위해서 난이도를 first 값으로 만들어주었다.

그 이외에는 나머지 언급해 준 것과 같다.

 

 

---

시행착오

처음에는 vector로 풀어서 전체 문제를 그대로 탐색해 버려서 시간초과를 피할 수가 없었다.

그리고 map을 사용하는 것에 익숙하지 않았기 때문에 웬만하면 map 사용을 피했다.

그거 때문에 틀린 것 같다.
평소에 map 사용법을 잘 익혀놔야 할 것 같다.

해당 문제를 풀면서 어느 정도 익숙해진 것 같다.

 

생활비..

https://toss.me/howudong

howudong님에게 보내주세요