Hash - 완주하지 못한 선수

이번 포스팅은 Hash를 이용한 빠른 탐색 문제에대한 포스팅 입니다.

programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

해당 문제를 살펴보면, 다수가 참가한 경기에서 한명만이 낙오가 발생하였고

 

해당 낙오자가 누구인지 찾는 문제입니다.

 

간단히 생각하면, 참가자를 Sorting하고, 완료자를 Soring해서

 

index순으로 비교하면 답은 찾을 수 있습니다.

 

하지만, 두개의 List를 Sorting하고 indexing순서만큼 비교한다고 치면(정렬에 nlogn이라고 가정)

 

시간복잡도가 O(nlogn) + O(nlogn) + O(n)이되어, 효용성 테스트를 통과할수가 없습니다.

 

 

 

이때 해당 문제의 범주가 Hash임을 생각해봅니다.

 

완주자들의 이름은 특정 범주로 묶고, 줄여놓은 범주 내에서 참가자의 이름을 찾을 경우

 

Search에 걸리는 시간을 상수수준으로 감소시킬 수가 있습니다.

 

이때 범주로 묶을때 Hash변환을 사용하여, 묶은 범주를 HashTable로 사용하면 됩니다.

 

저같은 경우 완주자의 이름은 Python 내장 hash함수로 변환한 후 0~200사이의 값으로 변환하였습니다.

 

이렇게 만들어진 HashTable을 가지고 참가자의 이름이 있는지 여부를 확인하면 되겠습니다 :)

 

아래는 Hash를 활용한 Python코드 해답입니다.

def solution(participant, completion):
    answer = ''    
    #HashTable의 갯수 설정
    hash_count = 200
    #Dictionary를 이용해 HashTable사용
    comp_htable = {i : [] for i in range(hash_count)}    
    for i in completion:
    	#참가자의 이름으로 Hash변환 후 0~199사이의 값으로 변환
        hash_key = divmod(hash(i),hash_count)[1]
        #HashTable에 참가자의 이름은 삽입합니다.
        comp_htable[hash_key].append(i)
       
    #이제 참가자의 이름이 HashTable에 있는지 확인합니다.
    for i in participant:
    	#이때 참가자의 이름이 없으면 Loop를 멈추고, 정답을 반환합니다.
        if i not in comp_htable[divmod(hash(i),hash_count)[1]]:        
            answer = i
            break
        #동명이인이 있을경우 알고리즘의 문제발생을 방지하기 위해서
        #Search가 끝난 이름은 제거해줍니다.
        else:            
            comp_htable[divmod(hash(i),hash_count)[1]].remove(i)
    return answer