프로그래머스 완주하지 못한 선수 JAVA 풀이 (HashMap, 해시)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

마라톤 참가자 명단(participant)과 완주자 명단(completion)이 주어진다.

완주자 명단은 참가자보다 한 명 적으며, 완주하지 못한 선수의 이름을 반환하는 문제이다.

 

참가자 중에는 동명이인이 존재할 수 있기 때문에 단순 비교만으로는 해결할 수 없다.

---

📌 접근 방법

이 문제는 이름의 등장 횟수를 관리하는 것이 핵심이다.

HashMap<String, Integer>를 사용하여 참가자의 이름을 Key, 등장 횟수를 Value로 저장한다.

 

이후 완주자를 순회하면서 해당 이름의 개수를 1씩 감소시키면, 마지막에는 완주하지 못한 선수만 값이 1로 남게 된다.

마지막으로 HashMap을 순회하여 값이 0이 아닌 Key를 반환하면 된다.

---

📌 핵심 아이디어

1. 참가자의 등장 횟수 저장

• 이름이 처음 등장하면 1을 저장한다.
• 이미 존재하는 이름이면 기존 값에 1을 더한다.
• 동명이인도 정확하게 처리할 수 있다.

map.put(participant[i], map.getOrDefault(participant[i], 0) + 1);

---

2. 완주자의 등장 횟수 차감

완주한 선수의 개수를 하나씩 감소시킨다.

map.put(completion[j], map.get(completion[j]) - 1);

 

 

leo -> 1
kiki -> 1
eden -> 1

↓

leo -> 1
kiki -> 0
eden -> 0

---

3. 값이 남아있는 선수가 정답

값이 0이 아니라면 해당 선수가 완주하지 못한 선수이다.

for(String key : map.keySet()){
    if(map.get(key) != 0){
        answer = key;
    }
}

---

📌 전체 코드

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";

        HashMap<String, Integer> map = new HashMap<>();

        for(int i = 0; i < participant.length; i++){
            map.put(participant[i], map.getOrDefault(participant[i], 0) + 1);
        }

        for(int j = 0; j < completion.length; j++){
            map.put(completion[j], map.get(completion[j]) - 1);
        }

        for(String key : map.keySet()){
            if(map.get(key) != 0){
                answer = key;
            }
        }

        return answer;
    }
}

 

---

📄 정리

• HashMap을 이용한 빈도수 카운팅 문제이다.
• getOrDefault()를 사용하면 등장 횟수를 간단하게 관리할 수 있다.
• 완주자는 개수를 감소시키고, 마지막에 값이 남아있는 선수를 찾으면 된다.
• 동명이인이 존재하는 경우도 정확하게 처리할 수 있다.
• 시간복잡도는 O(N) 으로 대용량 데이터도 효율적으로 처리할 수 있다.