[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> cnt = new HashMap<>();
        for (String p : participant) {
            cnt.put(p, cnt.getOrDefault(p, 0) + 1);
        }
        for (String c : completion) {
            cnt.put(c, cnt.getOrDefault(c, 0) - 1);
        }

        for (Map.Entry<String, Integer> e : cnt.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> cnt;
    for (string& p : participant) cnt[p]++;
    for (string& c : completion) cnt[c]--;

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

    return "";
}

from collections import Counter


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

Counter(participant)와 Counter(completion)은 각각 이름을 키로, 등장 횟수를 값으로 갖는다. 두 Counter를 빼면 이름별 카운트가 상쇄되고, - 연산자는 결과가 0 이하인 항목을 버리므로 완주한 선수는 모두 사라지고 완주하지 못한 선수만 카운트 1로 diff에 남는다.

---