문제

풀이

첫 번쨰 풀이

def solution(phone_book):
    phone_book.sort()
    
     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

첫 번쨰 풀이는 생각보다 오래 걸리지 않았다. 우선 사전적으로 phone_book을 정렬해준 뒤 이중 for문을 돌며 모든 두 쌍을 비교하는 방법이다. 이떄 startswith함수를 사용하여 접두사가 겹치는지 확인하고 겹치면 False, 그렇지 않음 True를 출력한다.
그러나 이 방법은 $O(n^2)$의 시간 복잡도를 가지기 떄문에 효율성 체크에서 막혀버렸다 ㅠㅠㅠ

두 번쨰 풀이

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
    
    return True

sort는 그대로 유지하며 sort의 장점을 활용하기로 했다. 어차피 문자열 배열이 정렬되면서 비슷한 문자열이 같이 배치되었을 것이고 겹치는 문자열의 갯수가 아닌 True, False값만 뱉어내면 되기 때문에 굳이 이중 for문을 돌지 않고 양 옆 문자열만 비교하는 방법을 채택했다. 이렇게 되면 nlog(n) 의 시간 복잡도를 갖는다!

회고

우선 어려운 문제는 아니었다. 딱히 예외 처리를 할 필요도 없어서 한 번 생각나면 쭉 풀수 있는 문제였던 것 같다.