[programmers/python] 마라톤 완주자 찾기 - collections.Counter

문제

• url : https://school.programmers.co.kr/learn/courses/30/lessons/42576
• 참가자 수: 1명 이상 100,000명 이하
• 이름: 알파벳 소문자, 길이 1~20자
• 완주자 수: 참가자 수 - 1
• 동명이인 존재 가능

---

예시

participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]
# 결과: "leo"

participant = ["mislav", "stanko", "mislav", "ana"]
completion = ["stanko", "ana", "mislav"]
# 결과: "mislav"

---

핵심 아이디어

이름이 중복될 수 있다. 단순 정렬이나 반복문만으로는 정확히 잡아내기 어렵다.
각 이름이 몇 번 나왔는지를 세야 한다. 여기서 collections.Counter가 유용하다.

• Counter는 리스트의 요소 개수를 세는 딕셔너리 기반 자료구조다.
• 두 Counter의 차이를 구하면, 완주하지 못한 사람이 나온다.

---

코드

from collections import Counter

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

---

설명

• pc: 참가자 이름별 수량
• cc: 완주자 이름별 수량
• pc - cc: 참가자에서 완주자를 뺀 결과 → 딱 1명 남는다
• .keys()[0]: 남은 한 명의 이름 반환

---

시간 복잡도

• Counter 생성: O(N)
• 차이 계산: O(N)
• 결과 추출: O(1)
  → 전체 O(N), 매우 빠름