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

• 출처: 프로그래머스 42576
• 분류: 해시 · Lv.1

문제

마라톤 참가자 배열 participant와 완주자 배열 completion이 주어진다. 완주하지 못한 선수 한 명의 이름을 반환하라. 동명이인이 있을 수 있다.

핵심

두 배열의 차이를 구하는 문제. 해시맵에 참가자를 카운팅하고 완주자로 빼면 남는 한 명이 답이다.

풀이

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> m;

    for (const auto& p : participant) m[p]++;
    for (const auto& c : completion) m[c]--;

    for (const auto& [name, cnt] : m)
        if (cnt > 0) return name;

    return "";
}

메모

• set이 아니라 map인 이유: 동명이인이 있을 수 있어서 존재 여부가 아니라 개수를 세야 한다.
• map이 아니라 unordered_map인 이유: 키 순서가 필요 없고, 조회가 O(log N) 대신 O(1).
• m[p]++: 키가 없으면 0으로 자동 생성되므로 존재 확인이 필요 없다.
• auto& [name, cnt]: C++17 구조화 바인딩. pair.first/second 대신 이름으로 접근.

정렬로도 풀 수 있다

string solution(vector<string> participant, vector<string> completion) {
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for (int i = 0; i < completion.size(); i++)
        if (participant[i] != completion[i])
            return participant[i];

    return participant.back();
}

정렬하면 같은 이름이 나란히 온다. 순서대로 비교해서 처음 다른 이름이 미완주자. O(N log N)이지만 추가 메모리가 필요 없다.

복잡도

풀이	시간	공간
브루트포스	O(N²)	O(1)
정렬	O(N log N)	O(1)
해시맵	O(N)	O(N)