[Programmers/알고리즘 고득점 KIT] 완주하지 못한 선수

[Programmers] 완주하지 못한 선수

Level 1 | #해시

문제 바로가기 🔗

1. 문제 요약

수많은 마라톤 선수들이 마라톤에 참여하였다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다.

참가자 명단(participant)과 완주자 명단(completion)이 주어질 때, 완주하지 못한 선수의 이름을 반환하는 문제이다.

2. 접근 방식 및 포인트

참가자 중 동명이인이 있을 수 있다는 점이 핵심이다. 단순히 존재 여부만 체크해서는 안 되며, 각 이름별 인원수를 관리해야 한다.

• ✅ 자료구조: Python의 dict(Hash Table)를 활용하여 이름별 인원수를 저장한다.
• ✅ 시간 복잡도: O(n) 이내에 해결해야 한다. participant와 completion을 각각 한 번씩 순회하므로 O(n)에 해당한다.

3. 구현 코드 (Python)

def solution(participant, completion):
    d = {}
    for people in participant:
        d[people] = d.get(people, 0) + 1
        
    for complete in completion:
        if complete in d:
            d[complete] += -1

    for key, value in d.items():
        if value != 0:
            return key

📌 딕셔너리 조회 방법: d.get(요소, 0)은 요소가 없으면 0을 반환하는 유용한 메서드이다.

📌 딕셔너리 순회: d.items()를 사용하여 for문에서 key와 value를 동시에 꺼내어 처리한다.

4. 리팩토링 - Counter 사용

Python의 collections.Counter를 활용하면 가독성을 훨씬 높일 수 있다.

from collections import Counter

def solution(participant, completion):
    return list((Counter(participant) - Counter(completion)).keys())[0]

Counter 객체 간의 뺄셈 연산 결과, 값이 0 이하인 키는 자동으로 제외된다.

결과적으로 남은 키 리스트에서 첫 번째 원소([0])를 반환하면 완주하지 못한 선수를 찾을 수 있다.

[예시] Counter 결과값

Counter({'leo': 1, 'kiki': 1, 'eden': 1})