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

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

Solution

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

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> d;
    for(auto& i : participant) d[i]++;
    for(auto& i : completion) d[i]--;
    for(auto& i : d){
        if(i.second > 0){
            answer = i.first;
            break;
        }
    }
    return answer;
}

unordered map과 map의 차이가 뭘까? 기존의 map은 key의 값을 기준으로 데이터가 저장된다. 그렇지만 unordered_map은 key의 해시 값을 기준으로 데이터가 저장된다.
특별히 데이터가 정렬되어서 저장되어야 하는 상황도 아니고 말 그대로 특정한 데이터에 대한 값만 저장하고 있으면 된다. 그러므로 성능 면에서 unordered_map 이 조금 더 유리하다고 한다.
뭐 사실 이 문제 같은 경우엔 어렵게 생각할거 없다. 굳이 unordered_map 씩이나 쓸 것도 없다. 그렇지만 조금 무지성으로, 스마트하지 못한 방법을 쓴다면 2중 for문으로 처리해야겠지.
참여자 데이터가 최대 100000명이다. 만약 무지성으로 2중 for문 처리를 한다면 시간초과가 날 수도 있다. 즉 데이터 처리를 최대한 빠르게 하려면 좀 더 진보적인 방법을 써야한다.

map에 대해서는 따로 설명하지 않겠다. for each문을 통해 각 participant들의 데이터들을 map에 갱신한다. 각자 참여했다는 의미로 1씩 데이터를 넣어준다.
그리고 completion 데이터에 접근하여 완주자들의 value를 1씩 줄여준다. 이렇게 처리하면 일일히 찾고 비교할 것 없이 빠르게 데이터를 처리할 수 있다.

그 이후로 map을 뒤져보면서 유일하게 value가 0이 아닌 녀석을 찾으면 그만이다. 간단하다.