[백준] 13414, 수강신청 (C++, 해시맵)

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

13414번: 수강신청

 

이번 주 스터디는 내 차례가 되어 조금 더 깊게 이 문제에 대해 공부해봤고,

이 문제를 풀어봄으로써 C++의 STL에 대해 조금 더 알게되었다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

// sort, unordered_map(해시맵), pair, auto, iterator

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

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int K, L; // 수강 가능한 인원, 대기 줄, 학번
    cin >> K >> L;
    
    vector<pair<string, int>> vt;
    unordered_map<string, int> student;
    for(int i=0; i<L; i++){
        string grade;
        cin >> grade;
        student[grade] = i;  // key : 학번, value : 인덱스(벡터에 넣어줄 거임)
    }
    
    for(pair<const string, int>& it : student){ // 해시 맵의 키 밸류를 하나로 받아옴.
        vt.push_back(it);
    }
    
    sort(vt.begin(), vt.end(), compare); // begin <= 범위 < end, compare = 정렬 기준(오름차순)
    for(int i=0; i<min(K, (int)vt.size()); i++){
        cout << vt[i].first << '\n';
    }
    
    
    return 0;
}

문제는 학번을 string으로 받아야 한다는 게 핵심이었다. (int로 받으면 안됨 ㅠ)

시간초과를 굉장히 많이 내는 문제기 때문에 수행시간이 가장 작은 해시맵을 이용하여

이론 상 O(1)에 가까운 자료구조 unordered_map 해시맵을 사용하였다.

---

이 문제를 통해 내가 배운 것은 다음과 같다.

 

sort, unordered_map(해시맵), pair, auto, iterator

다 알고있는 개념이지만, 개념만 알 뿐 실제로 쓸 줄은 몰랐다.

 

여태껏 배운 언어는 python, C, C++, Java, Kotlin 인데 자료구조를 다룬 건 자바와 C언어 뿐이고,

심지어 이마저도 C로는 구현, 자바는 선언하는 방법만 아는 수준이었다.

 

unordered_map이 C++의 해시맵이란 것을 알게 되었고,

이 자료구조의 원소를 접근할 때, 이터레이터 자료형으로 auto를 써도 되지만,

뭣도 모르면서 auto를 쓰기 싫어서 알아보니 그 안의 원소가 pair<const int, int>로 되어있다는 사실도 알게 되었다.

또한, 해시맵이므로 정렬이 안 되어 있어서 벡터에 넣고나서 벡터를 sort 해주었다.

 

sort 할 때, 세 번째 인자인 compare를 쓰는 방법과, compare 함수에서 인자들을 받는 방법 등등

이 문제를 통해 여러 자료구조에 대해 복습해볼 수 있었다.