해시(Hash) 대표 문제 풀이: 완주하지 못한 선수

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

프로그래머스

---

• 제한 조건이 중요하다
  • 보면 n의 수가 100000인데 이런 경우 보통 $O(n)$ 이나 $O(n\log n)$의 복잡도로 풀어야 한다.(파이썬은 1초에 대략 20000000만번의 연산 수행 이를 참고해 계산해 보면 편함)
• 자료구조(와 알고리즘) 의 선택
  • 만약 이름 대신 번호가 주어졌다면? -> 선형 배열(linear array) 이름의 경우의수가 많아질 수 있으므로 적합하지 않음
  • 📌 번호 말고 다른것(예: 문자열)로 접근 할 수 있는 좋은 자료구조는? -> key, value로 관리할 수 있는 hash형 구조가 적합
  • 해시(Hash)와 대응되는 파이썬 자료구조는 dictionary 형이 있다.
    • dictionary 자료구조 원소 조회 시간 복잡도는 $O(1)$
  • 직접 dict을 정의한 후 반복문을 통해 key, value를 구성해도 되지만 파이썬에는 이를 처리해주는 멋진 라이브러리가 있다. Counter를 이용하면 편하게 할 수 있다.

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]

📌 dictionary get함수에 대한 설명: https://wikidocs.net/16

02-5 딕셔너리 자료형

Counter 이용

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]