[백준] 13414번 수강신청 C++ 코드

코드

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

using namespace std;

int cnt, n, k;
unordered_map<string, int> mp;
string s;
vector<pair<string, int>> v;
vector<string> res;

void FASTIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

bool cmp(pair<string, int> a, pair<string, int> b) {
    return a.second < b.second;
}

int main() {
    FASTIO();
    cin >> k >> n;
    for(int i = 0; i < n; i++) {
        cin >> s;
        mp[s] = ++cnt;
    }
    for(const auto& e : mp) {
        v.push_back(make_pair(e.first, e.second));
    }
    sort(v.begin(), v.end(), cmp);
    int people = 0;
    for(int i = 0; i < v.size(); i++) {
        if(people == k) break;
        res.push_back(v[i].first);
        people++;
    }
    for(const auto& ret : res) {
        cout << ret << '\n';
    }
    return 0;
}

풀이

unordered_map에 들어온 순서로 기록을 해주었다. 그 후에 벡터에 넣고, 신청번호 순으로 정렬했다. 그 후 정원까지 출력하여 해결했다. 해시충돌이 나면 더 느릴 거 같아 처음엔 map을 이용했는데, unordered_map을 이용해도 문제는 없었다. 오히려 더 빨랐다. (260ms vs 388ms) unordered_map이 최악의 경우가 뜰 때가 언제인지 더 고민을 해봐야할 거 같다...