[코딩테스트] [프로그래머스] 완주하지 못한 선수

문제

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

---

풀이

1. 삽입/탐색 시 O(1)의 시간복잡도로 풀이하기 위해 unordered_map을 사용했다. 해당 unordered_map은 [key(선수 이름), value(선수 빈도)] 쌍을 관리한다.

2. 완주한 선수 벡터를 순회하며 unordered_map에 키-값 쌍을 삽입한다.

3. 참여한 선수 벡터를 순회하며 해당 키가 unordered_map에 있다면, 값을 감소시킨다.
   3-1. 만약 값이 음수라면, 같은 이름이더라도 완주하지 못한 선수이기에 반환할 string에 해당 값을 넣어준다.

4. 해당 키가 unordered_map에 없다면, 반환할 string에 해당 값을 넣어준다.

---

코드

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) 
{
    unordered_map<string, int> frequency;
    for (string name : completion)
    {
        if (!frequency.empty())
        {
            auto search = frequency.find(name);
            
            if (search != frequency.end())
            {
                search->second++;
                continue;
            }
        }

        frequency.insert({name, 1});
    }
    
    string answer = "";
    for (string name : participant)
    {
        auto search = frequency.find(name);
        if (search != frequency.end())
        {
            search->second--;
            if (search->second < 0)
            {
                answer = name;
                break;
            }
        }
        else
        {
            answer = name;
            break;
        }
    }
    
    
    return answer;
}