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

문제 소개

오늘 풀었던 프로그래머스 - 완주하지 못한 선수 문제를 정리합니다.

이 문제는 마라톤에 참여한 선수 중 단 한 명, 완주하지 못한 선수를 찾는 문제입니다.
동명이인이 있을 수 있기 때문에, 단순한 포함 여부 체크가 아니라 이름의 등장 횟수를 정확히 비교하는 것이 핵심입니다.

문제 링크: 완주하지 못한 선수 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. HashMap을 이용하여 참가자의 이름과 등장 횟수를 기록합니다.
2. 완주자의 이름을 하나씩 처리하면서 등장 횟수를 차감합니다.
3. 등장 횟수가 0이 아닌 선수가 완주하지 못한 선수입니다.

---

해결 과정 및 코드

핵심 아이디어

1. 참가자 이름을 HashMap에 저장하고, 완주자 이름을 만나면 값을 감소시킨다.
2. 최종적으로 값이 0이 아닌 이름을 찾아 반환한다.

코드

시간 복잡도 : 최대 O(N) ( 참가자 수만큼 put )

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        // 참가자 이름 : +1 
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        // 완주자 이름 : -1
        for (String player : completion) hm.put(player, hm.get(player) - 1);
        // 0이 아닌 참가자 탐색
        for (Map.Entry<String, Integer> player : hm.entrySet()) {
            if (player.getValue() == 0) continue;
            answer = player.getKey();
            break;
        }
        return answer;
    }
}