[Algorithm] Programmers 완주하지 못한 선수 (Hash)

c++ 에는 Hash map 라이브러리가

<이름, 갯수> 형태로 자료구조를 만들어 갯수를 비교해 남은 선수 한 명의 이름을 구할 수 있다.
c++에는 std::map과 std::unordered_map 컨테이너가 있고 둘 다 key로 value에 접근 할 수 있다. map은 Red-Black Tree를 사용해 키의 순서를 유지하므로 탐색 속도에 시간복잡도 O(log n)을 가지는 반면 unordered_map은 Hash Table을 사용해 키의 순서를 유지하지 않는다. key 분포에 따라 탐색 속도에 O(1) 이상의 시간 복잡도를 가진다.

이 문제에서 자료구조의 이름이 정렬되어있을 필요가 없기 때문에 더 빠른 성능을 가지는 unordered_map을 쓰는 것이 적합하다.
c++에는 <hash_map>이 있긴 하지만 비공식적인 라이브러리이다. 이후에 해시맵을 지원하고자 나온 공식적 라이브러리가 이전의 hash_map과 매우 유사한 unordered_map 이다. 유사하다고는 하지만 성능면에서 훨씬 우수하므로 unordered_map만 사용하면 될 것 같다.

새로 공부한 c++문법 두가지가 있다.

1. auto : 변수 선언이 타입을 자동으로 추론하게 해주는 기능. 초기값을 지정하는 변수 선언에만 사용 가능!    [사용 예 ) for(auto it = vec.begin(); it!= end(); ++it) { ... } ]
2. ranged for loop : 범위기반 for문. 컨테이너의 순회는 늘 begin() 에서 end() 까지 ++it로 이루어지므로 이를 패턴화 시켜 for( auto it:vec) 으로 사용할 수 있다. it값으로는 vec 안의 값을 바꿀 수 없고 vec를 수정하고 싶다면 레퍼런스를 이용해 for(auto& it:vec)으로 쓰면 된다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> prtcpt_map;
    for(string name: participant){
        prtcpt_map[name]++;
    }
    for(string name: completion){
        prtcpt_map[name]--;
    }
    for(auto pair: prtcpt_map){
        if(pair.second>0){
            return pair.first;
        }
    }
}

참고https://bab2min.tistory.com/325
https://boycoding.tistory.com/226
https://jhnyang.tistory.com/120