전화번호 목록

문제

풀이

첫 번째 풀이

for i in range(len(phone_book)):
        for j in range(len(phone_book)):
            if i == j:
                continue
            if phone_book[i] in phone_book[j] and phone_book[i][0] == phone_book[j][0]:
                    return False
    return True

14번 테스트 케이스가 틀렸고 효율성 3,4번이 시간 초과이다. O(n^2)으로 최악의 경우에 이중 for를 끝까지 돌아야 하니까 시간 초과가 날 수 있다는 것은 인지를 했다.

도저히 14번이 왜 틀린지 반례를 못찾고 있었는데 정현이 형이 가르쳐줬다. 너무 멍청했다.

반례 => phone_book = ['123', '13123']
문자열이 안에 들어가있고, 첫 번째가 맞다고 해도 접두사가 아닐 수 있다. 그렇다고 문자열이 안에 들어가있을 때 문자열의 길이만큼을 다시 비교하는건 또 더 말이 안된다.

두 번째 풀이

phone_book.sort()
    for i in range(len(phone_book) - 1):
        if phone_book[i] == phone_book[i + 1][0:len(phone_book[i])]:
            return False
    return True

phone_book이 ["119", "97674223", "1195524421"] 와 같을 때 이는 문자열로 이루어진 배열이므로 정렬 시키면 ['119', '1195524421', '97674223'] 와 같다. 따라서 하나의 원소당 앞자리부터 비교를 할 수 있고 ( 이 때 [0:len(phone_book[i])] 으로 앞 원소의 길이만큼만 비교하면 된다)

세 번째 풀이

hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    
    for phone_number in phone_book:
        temp = ""

        for number in phone_number:
            temp += number

            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

문제의 원래 출제의도에 맞게 해시 맵(dictionary)을 이용해서도 풀 수 있다.