[프로그래머스 코딩테스트 고득점Kit] 해시 전화번호 목록

 

처음에는 완전 나이브 하게 코드를 짰었다.

    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            if len(phone_book[i]) > len(phone_book[j]):continue
            
            if phone_book[i] == phone_book[j][0:len(phone_book[i])]:
                print(phone_book[i])
                return False

하지만 시간복잡도가 O(N^2)이다 보니 효율성 테스트에서 떨어지는 문제가 발생했다.

 

def solution(phone_book):
    n = len(phone_book)
    phone_book.sort()
    
    for i in range(1,n):
        if phone_book[i-1] in phone_book[i]
                return False
            
    return True

위와 같이 수정을 하였으나 이는 접두사가 아닌 경우도 고려하기 때문에 정답이 될 수 없다.

 

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

따라서 위같이 함으로써 문제를 해결할 수 있었다.