해시 완주하지 못한 선수

기존에는 그저 list 끼리 비교해서 존재 여부를 파악하였다
그러다 보니 n개 요소를 가진 list끼리 비교하면 O(n의제곱) 의 Time Complexity를 가진다.

def solution(participant, completion):


    #dictionary = {string : i for i,string in enumerate(completion)}   
    
    for i in participant :
        if i not in completion :
            return i
    for i in participant :
        if participant.count(i) > 1 :
            if participant.count(i) != completion.count(i) :
                return i

그러나 답은 맞았지만 시간제한에서 걸렸다
그래서 빠른 조회를 위해서 Hash Table를 사용하기로 했다.
파이썬의 자료구조 중 Dictionary는 Hash로 구현된 자료구조 이다.
따라서 기존의 list를 Dictionary형태로 바꾼후에 조회하였다
Hash의 조회 Time Complexity는 O(1) 이다.

def solution(participant, completion):


    dictionary = {string : i for i,string in enumerate(completion)}   
    
    for i in participant :
        if i not in dictionary :
            return i
    for i in participant :
        if participant.count(i) > 1 :
            if participant.count(i) != completion.count(i) :
                return i