[프로그래머스/C++]Lv.1 - 완주하지 못한 선수

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42576

내 풀이

map을 이용하여 value값이 0이 아닌 선수를 찾는다.

내 코드

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    map<string, int> part;
    for(const string& s : participant)
        part[s]++;
    for(const string& s : completion)
        part[s]--;
    
    for(auto [f,s] : part)
        if(s > 0)
            answer += f;
    return answer;
}

다른 사람의 풀이

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> strMap;
    for(auto elem : completion)
    {
        if(strMap.end() == strMap.find(elem))
            strMap.insert(make_pair(elem, 1));
        else
            strMap[elem]++;
    }

    for(auto elem : participant)
    {
        if(strMap.end() == strMap.find(elem))
        {
            answer = elem;
            break;
        }
        else
        {
            strMap[elem]--;
            if(strMap[elem] < 0)
            {
                answer = elem;
                break;
            }
        }
    }
    return answer;
}

다른 사람의 풀이 해석

다양한 풀이가 있는데 hash를 쓰는방식이 가장 문제에 맞는 해답이라 생각하여 가져왔다.
시간복잡도가 O(log n)인 map 을 쓴 내 풀이에서
시간복잡도가 O(1)인 unordered_map을 쓰면 된다.