owel의 블로그

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

• 태그:
  • PS

문제 링크

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

풀이 아이디어

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

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

완주자 배열을 순회하며 같은 원소를 참가자 배열에서 찾는 과정에서, 완주자 원소당 탐색 비용이 O(n)인 것이 문제인데
이를 해결하기 위해 HashMap 같은 HashTable 계열 Collection을 사용하면 탐색 비용을
평균 O(1), 최악의 경우에도 O(log n)으로 줄일 수 있습니다.
(Java 8 이상에서는 해시 충돌이 많을 경우 내부적으로 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만 번으로 안정적인 통과가 가능합니다.

한편, HashSet을 사용할 경우 중복이 제거되어 문제 조건에 나온 동명이인에 대비할 수 없습니다.
그러므로 HashMap을 사용하여 참가자 명단의 각 이름을 Key로, 등장 횟수를 Value로 저장합니다.
이후 완주자 명단을 순회하며 같은 이름의 등장 횟수를 1씩 줄여나가면
최종적으로 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 "";
    }
}