해쉬 LV2 - 전화번호목록

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예제
phone_book return
["119", "97674223", "1195524421"] false
["123","456","789"] true
["12","123","1235","567","88"] false

입출력 예 설명
입출력 예 #1
앞에서 설명한 예와 같습니다.
입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

과정

이 문제를 풀고자 해쉬를 이용해보고자했지만 잘생각이 나지않아 이중for문을 사용했다.

def solution(phone_book):
    
    for i in range(len(phone_book)):
        for j in range(i+1,len(phone_book)):
            if phone_book[i] in phone_book[j] : return False
            if phone_book[j] in phone_book[i] : return False
            
    return True

결과는 실패..... python에 startswith이라는 앞부분 접두어 비교에 좋아보이는 함수가 있는 것을 깨닫고 반영해보았지만 정답은 맞았지만 시간문제로인해 실패하였다.

def solution(phone_book):
    
    for i in range(len(phone_book)):
        for j in range(i+1,len(phone_book)):
            if phone_book[i].startswith(phone_book[j]) : return False
            if phone_book[j].startswith(phone_book[i]) : return False
            
    return True

(아마 sort() 쓰면 시간문제 해결했을 수도??)

성공

시행착오끝에 해쉬문제인 만큼 해쉬를 사용해야할 것 같아서 해쉬를 사용했다.

def solution(phone_book):
    
    dic = {} 
    for phone_number in phone_book: 
        dic[phone_number] = 1 
        
    for phone_number in phone_book: 
        temp = "" 
            
        for number in phone_number: 
            temp += number 
            if temp in dic and temp != phone_number: 
                return False 
    return True

사실 직접구현했다기 보단 인터넷서핑으로 참고를 좀 했다.
딕셔너리를 먼저 구현하고 딕셔너리에 {["123",1],["456",1],...}이렇게 넣어주고 (string이 key값이 되도록 한다.)
temp로 접두어를 구현해나가면된다.

참고

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

이런 코드가 있었다... 정말 깔끔한 듯 먼저 정렬을 해주고 맨처음 것을 제외한 나머지 부분을 연결 후 p1으로 시작하는지를 비교해서 접두어로 존재하는지 판단을 해준다.(라고 추청)
이게 인접한 놈들만 비교를 하는건데 이게 첨엔 되나? 싶었는데 가능한 것 같다.