[프로그래머스][C++] 완주하지 못한 선수

완주하지 못한 선수

문제 링크

완주하지 못한 선수

분석

participant는 참가자 목록을 의미하며, completion은 완주자 목록을 의미합니다.
여기에서 참가자와 완주자에는 동명이인이 존재할 수 있습니다.

완주자는 참가자보다 정확히 1명이 적으며, 이 단 1명만 완주하지 못한 상태입니다.
여기서 완주하지 못한 사람을 찾아내야하는 문제입니다.

이 문제는 단순하게 존재 여부를 확인하기보다 동일한 이름이 여러번 등장할 수 있기 때문에 각 이름의 개수를 관리해야합니다.

단순하게 이중 반복문을 사용할 경우 시간 복잡도가 $O(n^2)$이 되어 시간 초과가 되기 때문에 좋은 방법이 아닙니다.
저의 경우 이름을 Key로 사용하고, 등장 횟수를 의미하는 Value로 해시맵을 사용하는 방법을 선택했습니다.

participant를 순회하여 각 이름의 개수를 증가시키고, completion를 순회하여 해당 배열에 존재하는 이름의 개수를 감소시키면 마지막에 0이 아닌 이름이 완주하지 못한 참가자의 이름이 될겁니다.

풀이

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    unordered_map<string, int> completionMap;
    
    // 참가자 이름의 개수 확인
    for (const auto& e : participant)
    {
        completionMap[e] += 1;
    }
    
    // 완주자 이름 확인
    for (const auto& e : completion)
    {
        if (completionMap.find(e) != completionMap.end())
        {
            completionMap[e] -= 1;
        }
    }
    
    // 완주하지 못한 이름을 찾는다.
    for (const auto& e : completionMap)
    {
        if (e.second == 1)
        {
            answer = e.first;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• participant를 순회하는 반복문 $O(n)$
• completion를 순회하는 반복문 $O(n)$
• unordered_map을 순회하는 반복문 $O(n)$
• $O(n) + O(n) + O(n)$

공간 복잡도는 $O(n)$입니다.

• 모든 이름이 서로 다를 경우 unordered_map $O(n)$

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.01ms, 4.11MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.18ms, 4.43MB)
테스트 4 〉 통과 (0.35ms, 4.14MB)
테스트 5 〉 통과 (0.33ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.17MB)
테스트 7 〉 통과 (0.01ms, 4.2MB)

효율성 테스트

테스트 1 〉 통과 (18.32ms, 17.7MB)
테스트 2 〉 통과 (30.57ms, 25.5MB)
테스트 3 〉 통과 (35.62ms, 30MB)
테스트 4 〉 통과 (43.04ms, 32.5MB)
테스트 5 〉 통과 (46.34ms, 32.5MB)