백준 13414 - 수강신청(C++)

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

13414번: 수강신청

 

풀이

온갖 STL을 떡칠한지라 ;; 당연히 시간 초과가 날 줄 알았으나 그렇지 않았다.

map과 set에 대해서는 꽤 안다고 생각했는데 이 문제를 풀면서 배운 것이 많아서 정리한다.

 

set을 사용하자니 입력값인 학번들이 입력 순서대로가 아니라 학번 순서로 정렬될 테니 적합하지 않았고,

vector를 사용하자니 탐색이 너무 느릴 것 같았다.

그래서 unordered set을 사용하려 했는데 입력값들이 랜덤한 순서로 저장되어 이것도 적합하지 않았다.

unordered set에 삽입한 결과

 

그래서 map에 학번(key), 입력순서(value)를 저장했다.

이때 학번이 0으로 시작할수도 있으므로 int 타입이 아니라 string 타입이어야 한다.

map에 이미 입력되어 있는 학번이 들어오게 되면, 입력 순서를 갱신했다.

모든 입력이 끝나면, value는 정렬되어있지 않으므로 vector에 복사해서 value 순서로 정렬했다.

그 후 수강 가능 인원만큼 출력해주면 끝!

 

코드

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(const pair<string,int>& a, const pair<string,int>& b)
{
    if(a.second<b.second) return true;
    else return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    map<string,int> s;
    for(int i=0; i<m; i++)
    {
        string id;
        cin>>id;
        if(s.find(id)!=s.end())
        {
            s[id]=i;
        }
        else s.insert({id,i});
    }
    vector<pair<string,int>> v(s.begin(),s.end());
    sort(v.begin(),v.end(),cmp);
    
    for(int i=0; i<n; i++)
    {
        if(i==v.size()) break;
        cout<<v[i].first<<'\n';
    }
}

 

배운 것

1. unordered_set은 삽입 순서대로 set에 삽입되는 것이 아니라 랜덤으로 삽입된다.

그럼 정렬도 되지 않는 set을 어디다가 쓰나 했더니 unordered_set / unordered_map은 해시함수를 사용해서 최고의 경우 탐색을 O(1) 만에 수행할 수 있다고 한다. 물론 해시함수 특성상, 원소들이 충돌하여 다 같은 값을 반환하게 되는 최악의 경우에는 O(N)의 수행 시간을 갖게 될 수는 있다. 하지만 이 상황은 많지 않을 것이므로 최적화가 필요한 경우에는 unordered_set/map을 사용하는 것도 좋을 것 같다.

이와 관련해서는 https://modoocode.com/224 포스팅을 참고했다.

 

2. vector에 map을 복사하려면 아래와 같이 해주면 된다.

vector<pair<string,int>> v(s.begin(),s.end()); //(s는 map의 이름)