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

강의

"해시"는 해시 테이블(Hash table)에 인덱스 대신 키를 활용하는 알고리즘 입니다.

key에 대한 value를 저장하는 칸을 해시 버킷(Hash bucket) 이라고 합니다.

다른 key의 value가 같은 해시 버킷에 지정되는 경우를 해시 충돌(collision) 이라고 합니다.

 

 

Step 1-3: 풀어서 내 것으로 만들자! 완주하지 못한 선수

⭐ 직관적 풀이 : 완주하지 못한 선수가 한명이기에 정렬을 이용하여 해결하는 방법!

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for i in range(len(participant)):
        if i > len(completion)-1:
            return participant[-1]
        
        if participant[i] != completion[i]:
            return participant[i]

⭐ 힌트 풀이 : 일반적인 경우를 예상하여 딕셔너리를 이용하여 해결하는 방법!

def solution(participant, completion):
	dict = {}
    
    for x in participant:
    	dict[x] = dict.get(x, 0) + 1
    
    for x in completion:
    	dict[x] -= 1
        
    name = [key for key, value in dict.items() if value > 0]
    
    return name[0]