완주하지 못한 선수

문제

풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    sort(participant.begin(),participant.end());
    sort(completion.begin(),completion.end());
    for(int i=0;i<completion.size();i++)
    {
        if(participant[i] != completion[i]) return participant[i];
    }
    return participant[participant.size()-1];
}

문제에 n은 10만이기 때문에 시간복잡도 $O(nlogN)$ 이하로 풀어야 한다고 먼저 생각을 했습니다.

그래서 sort의 경우에는 nlogN의 시간복잡도를 가졌기 때문에 사용해도 된다고 생각을 하고 사용을 하였습니다.

두개를 sort를 통해서 동일한 기준으로 확인을 하고 for문을 completion의 size만큼 즉 n-1만큼 돌게끔 해주었습니다.

둘을 비교하다가 이름이 다르다 하면 participant 쪽에 선수 이름이 완주하지 못한 선수 입니다.

해쉬 테이블을 사용한 프로그래머스의 정답

#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;
}