[BOJ / C++] 수강신청 (해시)

문제링크: https://www.acmicpc.net/problem/13414

 

1. 코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int k, l;
    cin >> k >> l;

    unordered_map<string, int> order; // {학번: 순서}

    for (int i = 0; i < l; i++) {
        string sid;
        cin >> sid;
        
        order[sid] = i; // 덮어쓰기로 마지막 순서만 기억
    }
    
    vector<pair<int, string>> list; // {순서, 학번}
    for (auto& i: order) {
        list.push_back({i.second, i.first});
    }
    sort(list.begin(), list.end()); // 클릭 순서로 정렬

    int num = min(k, (int)list.size()); // 형변환 필수(컴파일에러), OOB 에러 방지
    for (int i = 0; i < num; i++) {
        cout << list[i].second << '\n';
    }

}

 

 

2. 시간복잡도

unordered_map에 추가하는 것은 O(1)에 동작한다. 정렬에 가장 많은 시간이 소요되고 O(LlogL)이다. 5*10^5 * 20 < 10^8이므로 시간제한 1초내에 통과 가능하다. 

처음에 학번에 대한 순서를 vector의 인덱스로 저장하려고 했었는데  01234567 같이 0으로 시작하는 것을 정확히 담지 못하고, 또한 vector<int> a(100,000,000)이 필요한다. 4byte * 100MB = 400MB > 256MB로 메모리 초과가 발생한다. 그냥 map<string, int>로 해주면 된다. 500,000 * (8byte+4byte) < 256MB이므로 메모리 초과가 발생하지 않는다.

 

3. 분석

map이나 unordered_map을 써야한다. 중요한 부분은 순서를 마지막 순서로만 업데이트 하면 된다는 것이다. 괜히 set<pair<int, int> {순서, 학번}으로 해서 삭제하고, 추가하고 할 필요가 없다. 오히려 꼬이고 헷갈리기만 하니 'map[학번] = 순서'로 업데이트만 해주면 된다. 

 

문제에 보면 수강인원 K가 항상 L보다 작다는 말이 없다. 즉 가능인원보다 신청한 수가 더 적을 수도 있으므로 아래의 과정이 필요하다. 

int num = min(k, (int)list.size()); // 형변환 필수(컴파일에러), OOB 에러 방지

    for (int i = 0; i < num; i++) {

        cout << list[i].second << '\n';

    }

 

min 함수에서 size_t는 인자로 받을 수 없어서 컴파일 에러가 발생한다. 따라서 (int)로 형변환을 해서 비교해줘야한다.