[Algorithm: 해시] 프로그래머스 <완주하지 못한 선수>

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42576?language=java

프로그래머스

 

문제 설명

마라톤에 참여한 선수 목록과 완주한 선수 목록이 주어진다. 이때 단 한 명의 선수만 완주하지 못했으며, 그 선수를 찾는 문제이다.

참가자 배열 participant와 완주자 배열 completion이 주어지고, 동명이인이 존재할 수 있다는 점이 주의사항이다.

 

---

 

처음 접근

처음에는 단순하게 두 배열을 비교하는 방식으로 접근했다.

for (int i=0; i<participant.length; i++) {
    for (int j=0; j<completion.length; j++) {
        if (participant[i].equals(completion[j])) {
            
        }
    }
}

 

참가자 한 명마다 완주자 전체를 순회하면서 같은 이름을 찾고 제거하는 방식이었다.

 

문제점

이 방식은 직관적이지만 시간복잡도가 크다. participant와 completion의 길이가 최대 100,000이기 때문에
이중 반복문을 사용하면 O(n²)이 되어 효율성 테스트를 통과할 수 없다. 실제로 정확성 테스트는 통과했지만, 효율성에서 시간초과가 발생했다.

 

 

---

해결 방법

 

이 문제를 다시 생각해보면
"완주하지 못한 사람을 찾는다"는 것은 결국 참가자는 모두 추가하고 완주자는 제거했을 때 남는 사람을 찾는 문제라고 볼 수 있다.

 

이 구조를 자연스럽게 처리할 수 있는 자료구조가 필요했고, HashMap을 활용하기로 했다.

이름을 key로, 등장 횟수를 value로 저장하는 방식으로 접근했다.

1. 참가자 이름을 순회하면서 횟수를 증가시킨다.
2. 완주자 이름을 순회하면서 횟수를 감소시킨다.
3. 마지막에 값이 0이 아닌 이름이 완주하지 못한 선수이다.

 

예시

예를 들어 다음과 같은 입력이 있다고 하자.

participant = ["leo", "kiki", "leo"]
completion = ["leo", "kiki"]

 

참가자를 기준으로 map을 만들면

leo → 2
kiki → 1

 

완주자를 반영하면

leo → 1
kiki → 0

 

이때 값이 0이 아닌 leo가 완주하지 못한 선수이다.

 

 

---

구현 및 시행착오

 

1. HashMap 타입 지정 문제

초기에 아래처럼 작성했을 때 에러가 발생했다.

HashMap map = new HashMap<>();

 

이 상태에서는 map.get()의 반환 타입이 Object가 되기 때문에 정수 연산을 할 수 없었다.

 

이를 해결하기 위해 다음과 같이 타입을 명확하게 지정했다.

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

 

 

2. getOrDefault 이해

처음에는 getOrDefault가 익숙하지 않아 헷갈렸다. 

map.getOrDefault(name, 0)​

 

이 코드는 key가 존재하면 그 값을 가져오고, 없으면 0을 반환하는 역할을 한다.

따라서 처음 등장하는 이름은 1로 시작하고 이미 존재하는 이름은 기존 값에 1을 더하게 된다.

 

 

---

최종코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<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 (String name : participant) {
            if (map.get(name) > 0) {
                answer = name;
            }
        }
        
        return answer;
    }
}

 

---

 

정리

이 문제는 단순 탐색 문제가 아니라 HashMap을 활용한 카운팅 문제였다.

특히 동명이인이 존재한다는 조건 때문에 단순 비교가 아니라 횟수 관리가 필요했다.

 

배운 점

• 시간복잡도를 고려하지 않으면 쉽게 시간초과가 발생한다.
• HashMap은 빈도수 계산 문제에서 매우 유용하다.
• getOrDefault는 카운팅 로직을 간결하게 만들어준다.