[프로그래머스/Python] 해시 - 완주하지 못한 선수

📚 해쉬 구조

키(Key)와 값(Value) 쌍으로 이루어진 데이터 구조
Key를 이용하여 데이터를 찾으므로, 속도를 빠르게 만드는 구조
파이썬에서는 딕셔너리(Dictionary) 타입이 해쉬 테이블과 같은 구조

기본적으로는, 배열로 미리 Hash Table 크기만큼 생성해서 사용합니다. 공간은 많이 사용하지만, 시간은 빠르다는 장점이 있음

검색이 많이 필요한 경우, 저장, 삭제, 읽기가 많은 경우, 캐쉬를 구현할 때 주로 사용

👍 장점

데이터 저장/검색 속도가 빠름
해쉬는 키에 대한 데이터가 있는지(중복)확인이 쉬움

👎 단점

일반적으로 저장공간이 좀 더 많이 필요
여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요 (충돌 해결 알고리즘)

⏰ 시간복잡도

일반적인 경우(충돌이 없는 경우): O(1)
최악의 경우(모든 경우에 충돌이 발생하는 경우): O(n)

👩🏻‍🏫 모범 답안

def solution(participant, completion):
    answer = {}
    # {'leo': 1, 'kiki': 1, 'eden': 1}
    for i in participant:
        answer[i] = answer.get(i, 0) + 1
    # completion 에 포함되는 이름의 key 의 value 를 -1 한다. 
    for j in completion:
        answer[j] = answer[j] - 1
    # participant 에는 있지만 completion 에는 없는 이름만 value 가 1로 남게되니 그것을 리턴한다.    
    for k in answer:
        if answer[k] : return k

✏️ Python 문법

딕셔너리.get('a','Nothing')