[프로그래머스 lv 2] 전화번호 목록(해시)

어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 리턴한다. 일일히 이 값들을 비교하기에는 너무 많은 연산이 필요할 것 같다. 같은 값이 중복되어 들어있지 않다고 하니, 같은 길이를 가지는건 일단 다 제거를 해본다. <- 이렇게 하면 숫자들을 비교를 하지 못하게 되는 문제가 발생한다.

 

이중 for문이면 비효율적이지 않을까... 생각했는데 그냥 이중 for문을 사용했다.

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

 

물론 이러면 정확성은 다 맞지만 효율성에서는 2개 정도 통과가 안된다.

 

# 두 번째 시도

def solution(phone_book):
    answer = True    
    phone_book = sorted(phone_book)
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return answer

 

'정렬했을 때 접두사 관계는 반드시 인접한 두 원소에서만 나타난다' 라는 말이 맞을때 이 방법이 가능한 것 같다.

 

다른 분 풀이를 보니 dictionary를 사용해서 각 단어를 for문 돌리고 부분 문자열이에 속하는게 dictionary의 key에 있느냐로 두고 찾던데 그것도 흥미로워보였다.