[Programmers] #42576 - 완주하지 못한 선수 [Java][C++][Python]

문제 링크

---

1. 아이디어

참가자 명단 participant와 완주자 명단 completion이 주어질 때, 완주하지 못한 단 한 명의 이름을 찾으면 되는 문제다. 동명이인이 있을 수 있으므로 이름을 단순히 집합으로 비교하면 안 되고, 이름별 등장 횟수를 세야 한다. 해시맵에 participant의 각 이름을 카운트로 더하고 completion의 각 이름을 카운트에서 빼면, 완주하지 못한 선수의 이름만 카운트가 1로 남는다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = participant의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();

        for (String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1);
        }

        for (String c : completion) {
            map.put(c, map.getOrDefault(c, 0) - 1);
        }

        for (Map.Entry<String, Integer> e : map.entrySet()) {
            if (e.getValue() == 1) return e.getKey();
        }

        return null;
    }
}

#include <bits/stdc++.h>
using namespace std;

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

    for (string& p : participant) mp[p]++;
    for (string& c : completion) mp[c]--;

    for (auto& [k, v] : mp) {
        if (v == 1) return k;
    }

    return "";
}

from collections import Counter


def solution(participant, completion):
    diff = Counter(participant) - Counter(completion)
    return next(iter(diff))

Counter 간 뺄셈은 결과가 0 이하인 항목을 자동으로 제거하므로, diff에는 카운트가 1로 남은 완주하지 못한 선수의 이름 하나만 남는다.

---