프로그래머스 42576 완주하지 못한 선수 (C++)

문제 링크

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

풀이

참가자(participant) 목록에서 완주자(completion) 목록의 원소들을 지웠을 때 참가자 목록에 남은 원소가 완주하지 못한 선수입니다. 

 

참가자 수의 최대값이 10만 이므로 시간복잡도가 O(N²) 일 경우 10만 * 10만 = 10억 으로 시간초과가 발생합니다.

참가자 목록을 HashTable 기반의 자료구조에 복사하고, 완주자 목록을 순회하며 각 원소의 이름을 HashTable 목록에서 지워주는 방식으로 진행하면 O(N) 으로 풀 수 있습니다.  

 

그리고 이 문제에서는 동명이인이 있을 수도 있습니다.

Hash table 기반의 자료구조는 중복을 허용하지 않으므로, Key-Value 형태의 원소를 사용하여 Key는 선수 이름, Value는 등장 횟수로 설정하면 참가자 목록에서 완주자를 지울때마다 등장 횟수를 하나씩 지워주는 방식으로 처리할 수 있습니다.

코드

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> count;
    
    for (const string& name : participant)
        count[name]++;
    
    for (const string& name : completion)
        count[name]--;
    
    for (const auto& pair : count) {
        if (pair.second > 0)
            return pair.first;
    }
    
    return "";
}