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

1. 문제 요약

참가자 명단과 완주자 명단이 주어진다. 완주하지 못한 단 한 명의 이름을 찾는다.

제한사항

• 참가자 수 1 ~ 100,000
• completion의 길이는 participant보다 정확히 1 작다
• 이름은 알파벳 소문자 1~20자
• 참가자 중에는 동명이인이 있을 수 있다

2. 접근 과정

Map<String, Integer>로 이름별 인원 수를 관리한다.

1. 참가자를 세면서 이름별 카운트를 올린다
2. 완주자를 훑으며 카운트를 내린다
3. 카운트가 0보다 큰 이름이 답이다

3. 코드

import java.util.HashMap;
import java.util.Map;

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

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

        for (String name : completion) {
            map.put(name, map.get(name) - 1);
        }

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

        return "";
    }
}

시간복잡도: O(N) — 참가자 N번, 완주자 N-1번, 맵 순회 최대 N번. 해시 조회는 평균 O(1)이다.
공간복잡도: O(N) — 맵에 최대 N개의 서로 다른 이름.