[Programmers] 전화번호 목록(Python)

프로그래머스 Level.2 에 해당하는 전화번호 목록 문제에 대한 풀이입니다.
자세한 문제 내용은 아래 링크에서 확인하실 수 있습니다.
https://school.programmers.co.kr/learn/courses/30/lessons/42577

이중 포문을 활용한 풀이 방식

def solution(phone_book):
    answer = True
    phone_book.sort(key=len)
    
    for i in range(len(phone_book)):
        n = len(phone_book[i])
        for j in range(len(phone_book)):
            if i == j:
                continue
            if phone_book[j][:n] == phone_book[i]:
                return False
    return answer

이중 포문을 사용함에 따라 시간복잡도가 증가할 것이라는 예상을 하였지만, 역시나 테스트 케이스 정확성은 높으나, 시간효율 측면에서 시간초과가 발생하였다.

문자열을 sort() 하게 되면, 문자열의 알파벳 순서 혹은 숫자 순으로 오름차순 정렬된다. 이에 따라 한 번호가 다른 번호의 접두사인 경우라면, 이웃하게 된다.
정렬에 따라 이웃한 두 문자열이 있다고 할 때, 앞에 있는 문자열이 뒷 문자열의 접두어가 되기 위해서는 앞 문자열의 길이가 더 짧아야 가능하다.
이를 고려한 코드를 아래에서 제시할 수 있다.

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

python에서는 접두어를 판별하는 str 내장함수 startswith()가 존재한다.
startswith() 를 활용하면 쉽게 접두어 판별여부를 확인할 수 있다.

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