Hash - 전화번호 목록

이번 문제는, 해시를 이용한 문제입니다.

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

 

문제를 살펴보면

1. 사람들 끼리 전화번호가 중복되지 않고

2. A의 전화번호가 B의 전화번호 앞자리와 같은가?

를 보는 문제입니다.

이때, 119와 117465라는 번호가 있으면, 11까지는 같지만 119와 117이 다르기 때문에

 

이러한 경우는 119가 117465의 접두가사 아닙니다.

 

그렇다면, 가장 작은 크기의 전화번호 크기만큼을 번호 앞글자를 Hash Key로 사용하는 Hash Table을 구성하면

 

Hash Table내에는

1. Table Key 와 동일한 값을 갖는 Element가 존재안함

--> 탐색 실패(119와 117465의 앞자리 길이가 2인 Case)

2. Table Key 와 동일한 값을 갖는 Element가 존재하면서 Table의 길이가 1이다

--> 탐색 실패(앞자리가 중복되는 경우가 없는 Case)

3. Table Key 와 동일한 값을 갖는 Element가 존재하면서 Table의 길이가 2 이상이다

--> 탐색 성공

 

이때, 모든 Hash Key에 대해서 탐색이 실패하면, 앞글자를 탐색할 수를 1씩 증가시키며 알고리즘을 반복합니다.

 

아래는 정답 코드입니다 :)

def solution(phone_book):
    answer = True
    #전화번호의 최소길이와 최대길이를 확인합니다.
    test = 22
    maximum = 0
    for i in phone_book:
        if len(i)<test:
            test = len(i)
        if len(i)>maximum:
            maximum = len(i)            
    end = False
    #전화번호의 가장 짧은 길이만큼을 Hash key로 하는 Hash Table을 생성    
    #이때, 가장 짧은 길이에서 탐색이 안되면, 길이를 늘려서
    #최대길이가 될 때 까지 반복을 진행
    while True:        
        temp_result = {}        
        #Hash Key를 기준으로 Hash Table을 Update시켜줍니다
        for i in phone_book:                
            try:
                temp_result[i[:test]].append(i)
            except:
                temp_result[i[:test]] = [i]
        #완성된 Hash Table에서 Hash Key가 Hash key에 해당하는 Table에 있고
        #Table의 길이가 2 이상(Hash Key 말고 추가적인 Element가 있는지 여부)
        #일 경우 전화번호의 선두가 겹치므로, 알고리즘을 종료합니다.
        for i in temp_result:            
            if i in temp_result[i] and len(temp_result[i])>=2:                                
                answer = False
                end = True
                break
        if end == True or test > maximum:
            break
        #이 경우 해당 길이에서 탐색이 실패하였으므로, 길이를 1늘려서 반복합니다.
        else:
            test = test +1
    return answer