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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

짧은 순서대로 탐색하는 것이 유리하다. 짧은 것이 다른 것의 접두사가 될 확률이 높기 때문이다.

> 이렇게 생각했었는데 문자열대로 정렬하면 [12, 9, 123]일 때 [12, 123, 9]로 정렬된다. 자릿수별 아스키 코드로 정렬하기 때문이다. 이러면 i와 i+1만 비교하면 된다. 같은 숫자로 시작하는 것들끼리 몰리기 때문이다. 

따라서 문자열 기준으로 정렬한 후, i번째 수가 i+1번째 수의 접두사인지 확인한다. 단 한 개의 번호만 주어진 경우 무조건 자기 자신의 접두사이므로 예외로 처리한다. 

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