프로그래머스 알고리즘 문제 풀이 - 완주하지 못한 선수 (Java)

문제 링크

프로그래머스 - 완주하지 못한 선수

풀이 아이디어

참가자 명단과 완주자 명단을 비교하여, 딱 한 명 완주하지 못한 사람을 찾는 문제입니다.
두 명단이 각각 배열로 주어지는데, 완주자 명단을 순회하며 해당 완주자와 동일한 이름의 사람을 참가자 명단에서 지운다면 참가자 명단에 마지막으로 남는 한 사람이 완주하지 못한 사람이 됩니다.

참여 선수의 수는 최대 100,000명이므로, 처음에 주어진 배열을 그대로 사용한다면 완주자 한 명 마다 참가자 명단 전체를 순회해야 하기에 O(n²)의 시간복잡도를 가지게 됩니다.
이는 최대 선수 명수인 10만명의 경우, 100,000 × 100,000 = 100억 번의 연산으로, 일반적인 Java의 시간 제한 기준인 3천만 번을 훨씬 넘어서게 됩니다.

완주자 배열을 순회하며 같은 원소를 참가자 배열에서 찾는 과정에서, 완주자 한 명당 참가자 명단 전체를 탐색하는 비용이 O(n)인 것이 문제인데, 이를 해결하기 위해 HashMap 같은 HashTable 계열 Collection을 사용하면 탐색 비용을 평균 O(1), 최악의 경우에도 O(log n) 으로 줄일 수 있습니다. (Java 8 이상에서는 HashTable 계열 Collection 사용 시 해시 충돌이 많을 경우, 내부적으로 Red-Black Tree로 변환되어 최악 O(log n)이 보장됩니다.)
따라서 전체 시간복잡도는 평균 O(n), 최악 O(n log n)이 됩니다.

이 때, 최악의 경우를 계산하면:

n = 100,000
log₂(100,000) ≈ 16.6
n × log₂n ≈ 100,000 × 16.6 ≈ 1,660,000번

 

약 166만 번으로 안정적인 통과가 가능합니다.

 

HashTable 계열 Collection 중 HashSet을 사용할 경우 중복이 제거되어 문제 조건에 나온 동명이인에 대비할 수 없습니다.

그러므로 HashMap을 사용하여 참가자 명단의 각 이름을 Key로, 등장 횟수를 Value로 저장해야 합니다.

참가자 명단을 HashMap에 넣은 후, 완주자 명단을 순회하며 HashMap 에서 같은 이름(Key)의 등장 횟수(Value)를 1씩 줄여나가면, 최종적으로 HashMap에서 등장 횟수(Value)가 0이 아닌 참가자 이름(Key)이 완주하지 못한 선수의 이름이 됩니다.

정답 코드

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String p : participant)
            map.put(p, map.getOrDefault(p, 0) + 1);
        for (String c : completion)
            map.put(c, map.get(c) - 1);
        for (String key : map.keySet())
            if (map.get(key) != 0) return key;
        return "";
    }
}