프로그래머스 - 전화번호 목록 (hash)

• 출처 : https://nordic.icpc.io/ , 프로그래머스 해쉬 - 전화번호 목록

def solution1(phone_book):
    answer = True
    for i_index, i in enumerate(phone_book):
        for j_index, j in enumerate(phone_book):
            if (i in j or j in i) and i_index != j_index and len(i) < len(j) and i[:len(i)] == j[:len(i)]:
                answer = False
            elif (i in j or j in i) and i_index != j_index and len(i) > len(j) and j[:len(j)] == i[:len(j)]:
                answer = False
    return answer

해당 코드는 시간복잡도가 무시된 코드다.
해쉬라하면 딕셔너리를 사용해야하는데 해쉬라 보기도 애매하고 코드는 짧지만 시간복잡도, 문제의 이해가 부족한 코드이다. 간단히 설명하면 이중 포문으로 자신이 포함되어 있는 경우에 대해서 검사한다. 더 간단한 방법은 미리 길이별로 sort를 하면 코드도 줄고 if문도 하나다.
더욱 더 간단하게 answer이 False로 두지말고 return False를 해도 좋다.

def solution2(phone_book):
    answer = True
    phones = dict()
    for phone_num in phone_book:
        phones[phone_num] = 1
    for phone_num in phone_book:
        temp = ''
        for num in phone_num:
            temp += num
            if temp in phones and temp != phone_num: 
            #자신에게 파생된 것이 자신과 같으면 안된다.
                return False
    
    return answer

딕셔너리를 이용하여 전화번호 목록에 있는 전화번호를 딕셔너리의 키로두고 벨류를 1로 뒀다.
그 다음 전화번호 목록에 대한 이중 반복문으로 앞글자 하나하나를 추가해서 타 전화번호와 비교하여 같은게 하나라도 있으면 False다.