Updated:

Categories: ,

Tags: , ,

문제

풀이

바킹독님의 문제집 풀이 작성하려다가 물려버렸다.
조건이 묘하게 까다로우면서 번거롭게 되어있어서, 적당히 메모해가면서 풀지 않으면 엉킨다.
한번 차근차근히 잘 정리해보자.

  • recommend: 분류 내에서의 가장 어렵거나, 쉬운 문제 번호를 출력한다.
  • recommend2: 분류 상관없이 가장 어렵거나 쉬운 문제 번호를 출력한다.
  • recommend3: 최저/최고 난이도 조건 내에서 가장 어렵거나 쉬운 문제 번호를 출력한다.

관건이 되는 부분은 문제집을 어떻게 관리할 것인가인데, 나는 중첩 map을 이용해서 관리하기로 했다. (다만, 자세히는 모르지만 map은 중첩될수록 제곱비례로 느려진다고 한다.)

  • map<int, map<int, set<int>>> probDB; : probDB[분류][레벨]에 문제 번호들이 담긴다.

다만 이렇게만 해두면 나중에 solved 명령어처리가 어려워지므로, 문제번호로 분류와 레벨을 조회할 수 있는 배열을 만들었다.

  • pair<int, int> probinfo[100'002];: probinfo[문제번호]를 하면 {분류, 레벨}이 도출된다.

그럼 준비가 다 되었으니 add와 solved를 구현해보자.

add

1
2
3
4
5
6
7
8
9
10
11

cin >> P >> L >> G;
insertDB(P, L, G);

void insertDB(int P, int L, int G) {
  probinfo[P] = {G, L};
  if (probDB.find(G) == probDB.end())
    probDB.insert({G, map<int, set<int>>()});
  if (probDB[G].find(L) == probDB[G].end())
    probDB[G].insert({L, set<int>()});
  probDB[G][L].insert(P);
}
  • insertDB는 기존에 없던 분류, 레벨이 들어왔을 때 빈 분류, 레벨을 만들어주는 작업을 해준다.

solved

1
2
3
4
5

cin >> P;
auto [G, L] = probinfo[P];
probDB[G][L].erase(P);
if (probDB[G][L].empty()) probDB[G].erase(L);
if (probDB[G].empty()) probDB.erase(G);
  • 지웠을 때 레벨이나 공간에 남은 문제가 없을 때에는 같이 지워준다.
    이는 recommend에서 탐색을 편하게 하려고 한 것인데,
    안그러면 나중에 추천할 때 여기가 빈 map인지 아닌지 확인하는 작업이 필요하기 때문이다.

이어서 recommend를 구현해보자.
recommend는 특정 분류 내에서 최대 난이도, 최대 번호 혹은 최소 난이도, 최소 번호를 뽑아야 한다.

map에서 최대 원소를 뽑고 싶으면 .rbegin()으로 뽑을 수 있다. (아니면 prev(.end()))라는 번거로운 방법을 통해야 한다.)

1
2
3
4
5

cin >> G >> x;
if (x == 1)
  cout << *(probDB[G].rbegin()->second.rbegin()) << '\n';
else
  cout << *(probDB[G].begin()->second.begin()) << '\n';

최대를 뽑아야 할 때에는 최대 레벨의 최대 원소를 추출하고, 최소를 뽑아야 할 때에는 그 반대로 한다.

이어서 recommend 2인데, 여기서부터는 이제 분류가 의미가 없게 된다.

전략은 {레벨, 문제번호}로 구성되어 있는 pair를 들고다니면서 비교하는 것인데,
이렇게 하는 이유는 레벨이 같을 때의 처리를 간편하게 해주기 위함이다.
아니면 레벨에서 차이가 날 때와 레벨이 같을 때를 서로 나눠서 비교해줘야 하기 때문.

또, 그렇게 탐색한 결과가 처음과 같다면 결과가 없었으므로 -1를 출력해야 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

cin >> x;
pair<int, int> mxv = {0, -1};
pair<int, int> mnv = {102, 100'002};
for (auto &group : probDB) {
  if (x == 1) {
    auto gMxLevKV = group.second.rbegin();
    pair<int, int> gv = {gMxLevKV->first, *gMxLevKV->second.rbegin()};
    mxv = max(mxv, gv);
  } else {
    auto gMnLevKV = group.second.begin();
    pair<int, int> gv = {gMnLevKV->first, *gMnLevKV->second.begin()};
    mnv = min(mnv, gv);
  }
}
cout << (x == 1 ? mxv.second : mnv.second) << '\n';

마지막으로 recommend3에서는 하한을 둔 최저, 상한을 둔 최고를 알아내야 한다.
또한 그렇게 탐색을 했을 때 결과가 없는 경우도 처리를 별도로 해주어야 한다.

전략은 아까와 같지만, 판별하기 전에 레벨 제한을 먼저 검사하도록 한다.
근데 여기서 실수하기 쉬운 부분은 x==1일 때는 난이도가 L보다 크거나 같은 경우에만 통과해야 하지만 x==-1일 때는 난이도가 L보다 작은 경우만 통과해야 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

cin >> x >> L;
pair<int, int> mxv = {0, -1};
pair<int, int> mnv = {102, 100'002};
for (auto &group : probDB) {
  for (auto &level : group.second) {
    if (x == 1) {
      if (level.first < L) continue;
      pair<int, int> lv = {level.first, *level.second.begin()};
      if (lv < mnv) mnv = lv;
    } else {
      if (L <= level.first) continue;
      pair<int, int> lv = {level.first, *level.second.rbegin()};
      if (mxv < lv) mxv = lv;
    }
  }
}
if (x == 1)
  cout << (mnv.first == 102 ? -1 : mnv.second) << '\n';
else
  cout << (mxv.first == 0 ? -1 : mxv.second) << '\n';

이렇게 해서 풀면 644 ms가 걸리지만, 더 빠른 풀이도 얼마든지 있을 수 있다.

코드

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <bits/stdc++.h>
using namespace std;

string op;
int G, N, L, P, x;
pair<int, int> probinfo[100'002];     // 문제별 분류, 난이도 저장
map<int, map<int, set<int>>> probDB;  // probDB[분류][난이도]
void insertDB(int P, int L, int G) {
  probinfo[P] = {G, L};
  if (probDB.find(G) == probDB.end())
    probDB.insert({G, map<int, set<int>>()});
  if (probDB[G].find(L) == probDB[G].end())
    probDB[G].insert({L, set<int>()});
  probDB[G][L].insert(P);
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  while (N--) {
    cin >> P >> L >> G;
    insertDB(P, L, G);
  }
  cin >> N;
  while (N--) {
    cin >> op;
    if (op == "recommend") {
      cin >> G >> x;
      if (x == 1)
        cout << *(probDB[G].rbegin()->second.rbegin()) << '\n';
      else
        cout << *(probDB[G].begin()->second.begin()) << '\n';
    } else if (op == "recommend2") {
      cin >> x;
      pair<int, int> mxv = {0, -1};
      pair<int, int> mnv = {102, 100'002};
      for (auto &group : probDB) {
        if (x == 1) {
          auto gMxLevKV = group.second.rbegin();
          pair<int, int> gv = {gMxLevKV->first, *gMxLevKV->second.rbegin()};
          mxv = max(mxv, gv);
        } else {
          auto gMnLevKV = group.second.begin();
          pair<int, int> gv = {gMnLevKV->first, *gMnLevKV->second.begin()};
          mnv = min(mnv, gv);
        }
      }
      cout << (x == 1 ? mxv.second : mnv.second) << '\n';

    } else if (op == "recommend3") {
      cin >> x >> L;
      pair<int, int> mxv = {0, -1};
      pair<int, int> mnv = {102, 100'002};
      for (auto &group : probDB) {
        for (auto &level : group.second) {
          if (x == 1) {
            if (level.first < L) continue;
            pair<int, int> lv = {level.first, *level.second.begin()};
            if (lv < mnv) mnv = lv;
          } else {
            if (L <= level.first) continue;
            pair<int, int> lv = {level.first, *level.second.rbegin()};
            if (mxv < lv) mxv = lv;
          }
        }
      }
      if (x == 1)
        cout << (mnv.first == 102 ? -1 : mnv.second) << '\n';
      else
        cout << (mxv.first == 0 ? -1 : mxv.second) << '\n';

    } else if (op == "add") {
      cin >> P >> L >> G;
      insertDB(P, L, G);

    } else if (op == "solved") {
      cin >> P;
      auto [G, L] = probinfo[P];
      probDB[G][L].erase(P);
      if (probDB[G][L].empty()) probDB[G].erase(L);
      if (probDB[G].empty()) probDB.erase(G);
    }
  }
}

Leave a comment

You may also enjoy