[알고리즘] 해시_완주하지 못한 선수 Python

💡 강의 참고 전 코드 (성공)

def solution(participant, completion):
    answer = ''

    participant.sort()
    completion.sort()
        
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            answer = participant[i]
            break
    if answer == '':
        answer = participant[-1]

    return answer

통과는 했지만, 문제의 의도인 해쉬를 사용하지 않았다.
sort() 함수를 사용했기 때문에 시간복잡도는 O(NlogN)

💡 강의 참고 후 코드

def solution(participant, completion):
    answer = ''

    participant_dict = {}
    completion_dict = {}
    for x in participant:
        participant_dict[x] = participant_dict.get(x, 0) + 1
    for x in completion:
        completion_dict[x] = completion_dict.get(x, 0) + 1

    for key, value in completion_dict.items():
        participant_dict[key] -= value

    answer = [key for key, value in participant_dict.items() if value > 0]

    return ''.join(answer)

시간 복잡도 O(N)이 된다.

✔️ 새로 알게된 함수

1️⃣ get(x, 0) -> x라는 key가 없을 때 0 반환, 있으면 해당 value 반환
2️⃣ answer = [key for key, value in participant_dict.items() if value > 0] 형태로 작성 가능