풀이

접두사가 될 수 있는 가능성이 있으려면, 길이가 짧은 순으로 리스트를 정렬하고 앞에서부터 탐색해야 한다고 생각함.
그래서 정렬을 먼저 하고 시작했다.

그 후, for loop 을 돌면서 접두사가 되는지 확인하면 되는데, 단순하게 전부 탐색하면 효율성 테스트를 통과할 수 없을 것 같았다.

그래서 hash table을 만들어서 탐색을 O(1)로 하면 될 것 같았다.

검색한 것

문자열 slicing 검색함.
python에서 쉽게 문자열 쪼갤 수 있는 걸 알았는데, 문법이 기억이 나지 않았다.
string[0:targetLength]
뭐 이런 식으로 하면 된다.

코드

def solution(phone_book):
    # 정렬
    phone_book.sort(key=len)
    hash_table = {}
    
    # 맨 처음 가장 짧은 길이를 저장. min.
    min_len = len(phone_book[0])
    
    for target in phone_book:
        # loop마다 본인 정보를 hash table에 저장.
        hash_table[hash(target)] = target
        # min길이부터 +1씩 해서 본인 길이까지 hash table에서 검색.
        # 있으면 false, 없으면 true-계속 진행.
        for i in range(min_len,len(target)):
            try:
                if hash_table[hash(target[0:i])]:
                    return False
            except KeyError:
                print('key error')
                # 아무 동작 안 해도 됨.
                
    return True

원래 if else 로 했었는데, key error가 나오더라. 그 이유는 key 값이 없어서 접근을 못 하는 것.

그래서 try except로 해결해 주었다.