Even Idiots Can Make Game

백준 13414 S3 수강신청

Date/Lastmod
Section
PS
Title
백준 13414 S3 수강신청
Ps-Tags
해시 테이블
Solved
03-31/2504-01/25

#1 접근

#2 완전 탐색으로

우선 잘 모르겠으므로 완전탐색으로 접근한다 생각해 봤을 때, 각 학번이 중복되었는지 매 순간 완전히 파악하려면 학번별로 $L$만큼 순회해야 하므로 벌써 복잡도가 $O(L^2)$이며, $L^2=10^{10}$이므로, 주어진 제한 시간 1초를 넘길 것이다.

$L$의 범위로 보건데, 한 번의 순회 로 순서를 모두 알아내지 않는 이상, 시간 초과가 나는 문제이다.

#2 한번의 순회로 순서를 다 결정하기 (1)

핵심은 학번을 키로 하는 해시 테이블을 만들고, 값으로 해당 학번의 최종 상대 순서를 저장하는 것이다.

클릭한 순서를 기록한 대기목록을 한번 순회하면서, index라는 카운터 변수를 한 번의 순회마다 증가시킨다.

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

// 클릭한 순서를 기록한 대기목록
vector<string> seqs;

// 학번과 최종 상대 순서
unordered_map<string, int> umap;

int index = 0;

for (const string& num: seqs) {
  ++index;
  umap[num] = index;
}

이러면 중복된 것이 발견되더라도 항상 마지막 index로 업데이트 되기 때문에, 대기열의 끝으로 보낼 수 있다.

다이어그램으로 표시하면 아래와 같다.

왼쪽 seq의 원소를 하나 하나 순회하면서, umap의 키-값을 업데이트 해 나가면 된다.

이러면 마지막에 umap을 vector로 바꾼 후 정렬을 해 준 후에, 앞에서부터 K개를 출력해 주어야 한다.

복잡도는 클릭 대기열을 한 번 순회하는데 $L$, 정렬에 $L\log{L}$, 앞에서부터 $K$개 출력에 $K$가 드므로, $O(L + L\log{L} + K)$이고, 이는 대략 $O(L\log{L})$이다.

코드는 아래와 같다.

 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

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>

using namespace std;

int K, L;

vector<string> nums;
unordered_map<string, int> umap;

int main() {
  cin >> K >> L;
  nums.reserve(L);

  for (int l = 0; l < L; ++l) {
    string num; cin >> num;
    nums.push_back(num);
  }

  int index = 0;

  for (const string& num: nums) {
    // umap의 상대 순서 업데이트
    ++index;
    umap[num] = index;
  }

  // 최종 대기 순번
  vector<pair<string, int>> vec(umap.begin(), umap.end());

  sort(vec.begin(), vec.end(), 
    [](const auto& l, const auto& r) { 
      return l.second < r.second; // 값의 오름차순으로 정렬
    }
  );

  // 최대값 주의 
  for (int i = 0; i < min(K, (int)vec.size()); ++i) {
    cout << vec[i].first << '\n';
  }
}

#2 한번의 순회로 순서를 다 결정하기 (2)

다른 방법도 있다.

위 방식은 인덱스로 상대 순서만 관리하였는데, 리스트를 이용하여 실제 최종 대기열을 유지하는 방식으로 구현할 수도 있다.

[참고] 중복되는 항목에 대해서 최종 대기열의 중간 에서 삭제가 빈번하게 일어나므로 list를 선택한다.

이 경우, 내가 중복된 경우 리스트의 정확히 어디를 지워야 하는지 기억하고 있어야 하므로, unordered_map<string, list<string>::iterator>를 사용한다.

클릭한 순서를 기록한 대기목록을 순회하면서:

이 경우 정렬이 필요 없고, 클릭한 순서 목록을 한 번만 순회하면 되므로 $O(L)$이다. [^1]

[?] 하지만, 이상하게도 실제 제출시 시간은 더 오래 걸리는데, 아무래도 list의 캐시 미스 때문인 것으로 추정된다.

코드는 아래와 같다.

 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

#include <iostream>
#include <string>
#include <list>
#include <unordered_map>
#include <vector>

using namespace std;

int K, L;

vector<string> nums;
unordered_map<string, list<string>::iterator> umap;
list<string> seqs;

int main() {
  cin >> K >> L;
  nums.reserve(L);

  for (int i = 0; i < L; ++i) {
    string num; cin >> num;
    nums.push_back(num);
  } 

  for (const string& num: nums) {
    // 처음 보는 경우
    if (umap.find(num) == umap.end()) {
      seqs.push_back(num);
      umap[num] = --seqs.end();
    // 중복되어 보는 경우
    } else {
      // 위치를 알고 있으므로 지워준다.
      seqs.erase(umap[num]);

      seqs.push_back(num);
      umap[num] = --seqs.end();
    }
  }

  int count = 0;
  for (const string& num: seqs) {
    cout << num << '\n';
    ++count;
    if (count == K) {
      break;
    }
  }
}
comments powered by Disqus