[프로그래머스] 전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

hash를 이용하는 문제이지만 이전 문제와 마찬가지로 hash를 안사용해도 충분히 효율성 테스트 까지 통과합니다.

 

문제부터 요약하면, phone_book에 전화번호들이 있는데 이중에서 어떤 번호가 다른 번호의 접두사가 될 수 있다면 False, 전부 접두사가 될 수 없다면 True를 return 해야 합니다.

 

즉 solution(phone_book)에 

phone_book : 전화번호를 담은 배열

이 주어지면, 위의 조건에 따라 True, False를 return 해야 합니다.

 

<Solution>

phone_book을 정렬시킨 후에 이웃한 것들끼리만 비교하면 nlogn+n 즉 O(nlogn) 의 복잡도로 풀리는 문제입니다. 

 

물론 hash를 이용하면 아마 O(n)의 복잡도로도 가능할 것 같기는 합니다. 

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
        else:
            continue

    return True