[프로그래머스] 전화번호 목록 python/파이썬 (해시 사용)

해시를 이용한 코드

 

phone_book을 정렬해준다.

i번째가 i+1, i+2...의 접두사가 될 순 있지만 i-1의 접두사가 될 순 없다.

따라서 우리는 i, i+1만 비교해서 i가 i+1의 접두사인지 확인해주면된다.

 

i가 접두사이기 위해선 i+1보다 길면 확인 할 필요가 없다. => continue

i가 i+1보다 작을 경우 해당 번호(phone_book[i])를 키값으로 dictionary에 초기화 값을 넣어준다.

i가 i+1의 접두사인지 확인하기 위해 i+1을 앞부터 len(i) 만큼 잘라 일치하는지 확인해준다. (in을 이용해 dic에 값이 있는지 확인한다.)

 

사실 startwith을 이용하거나 단순히 문자열을 자르고 같은지 비교하는게 더 편한거 같고 가장 빠르게 생각이 났다. 하지만 해시를 이용하려고 최대한 생각한 결과 이와 같은 코드를 작성했다. 속도 측면에서 아무래도 해시를 사용하는게 조금 더 빠른거 같다. 조금 아리송한 문제다.

 

 

def solution(phone_book):
    dic = {}
    phone_book.sort()

    for i in range(len(phone_book)-1):
        if len(phone_book[i]) >= len(phone_book[i+1]):
            continue

        dic[phone_book[i]] = 1
        if phone_book[i + 1][0:len(phone_book[i])] in dic:
            return False

    return True