[C++] Programmers Lv. 1 "완주하지 못한 선수"

🔵 문제 링크

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

프로그래머스

 

🔵 알고리즘

1. participant 벡터를 이용해 "사람 - 명" 정보를 담고 있는 map을 만들고 map[name] 값을 증가시킨다.
2. completion 벡터를 순회하며 도착한 사람이면 map[name] 값을 감소시킨다.
3. map을 순회하여 특정 이름을 가진 사람(남아 있는 사람)이 1명 이상이면 완주하지 못한 사람으로 간주하여 이름을 반환한다.

 

🔵 코드

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> peopleByName;

    // "사람 - 명" 의 표를 만든다.
    for (string name : participant)
    {
        peopleByName[name]++;
    }
    
    // 도착자 수를 표에서 차감한다.
    for (string name : completion)
    {
        peopleByName[name]--;
    }

    // 1명 이상 남아 있는 경우 완주하지 못한 선수이다.
    for (string name : participant)
    {
        if (peopleByName[name] > 0)
            answer = name;
    }

    return answer;
}

 

🔵 시간 복잡도

participant 길이를 N이라 했을 때 시간 복잡도는 O(N)이다.