해시 대표 문제 해결: 완주하지 못한 선수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42576

• 제약 조건이 중요합니다
  • 보면 n의 수는 100000입니다. 이 경우 보통 $O(n)$ 또는 $O(n\log n)$의 복잡도로 풀어야 합니다.
• 데이터 구조(및 알고리즘) 선택
  • 이름 대신 번호가 주어진다면? -> 선형 배열 이름의 경우의 수가 많을 수 있으므로 적합하지 않음
  • 숫자가 아닌 다른 것(예: 문자열)으로 접근할 수 있는 좋은 데이터 구조는 무엇입니까? -> 키와 값으로 관리할 수 있는 해시형 구조가 적합하다.
  • 해시에 해당하는 Python 데이터 구조에는 사전 유형이 있습니다.
    • 사전 데이터 구조의 요소 검색 시간은 $O(1)$입니다.
  • 사전을 직접 정의한 후 루프문을 통해 키와 값을 조합할 수 있지만 Python에는 이를 처리하는 멋진 라이브러리가 있습니다. 카운터를 사용하여 간단하게 이 작업을 수행할 수 있습니다.

def solution(participant, completion):
    d = {}
    for x in participant:
        d(x) = d.get(x, 0) + 1
    for x in completion:
        d(x) -= 1
    dnf = (k for k, v in d.items() if v > 0)
    return dnf(0)

사전 가져오기 기능 설명: https://wikidocs.net/16

사용 카운터

from collections import Counter

def solution(participant, completion):
    d = Counter(participant)
    for i in completion:
        d(i) -= 1
    result = (k for k, v in d.items() if v > 0)
    return result(0)