[c++/알고리즘] 프로그래머스 완주하지못한선수

---

나의 풀이

#include <string>
#include <vector>
#include <map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    map <string, int> maraton;
	
    // 참여자의 value값을 1씩 증가한다
    for(int i =0; i < participant.size(); i++){
        maraton[participant[i]] += 1;
    }
    // 참여자중 완주자가 있을 경우 value값을 1씩 감소
    for(int i = 0; i < completion.size(); i++){
        maraton[completion[i]] -= 1;
    }
    // 최종적으로 value값이 0이상인(완주하지 못한)선수를 출력
    for(auto a : maraton){
        if(a.second > 0){
            answer = a.first;
        }
    }

    return answer;
}

---

풀이 검색하다가 알게된 것

C++ STL에는 std::map 과 std::unoredered_map 컨테이너가 있다.
둘다 key를 이용하여 value에 접근할 수 있다.
여기서 map은 Red-Black Tree를 사용해 키의 순서를 유지하므로 탐색 속도에 시간복잡도 O(log n)을 가진다.
반면 unordered_map은 Hash Table을 사용해 키의 순서를 유지하지 않기 때문 탐색속도에 O(1)이상의 시간복잡도를 가진다.

위의 문제는 정렬을 하지 않기 때문 map 보다 unordered_map의 사용이 더욱 적합하다.