입력 배열을 사전순으로 정렬한 결과가 ["119", "1291", "2345", "3456"]라고 생각해 보겠습니다.
작성해 주신 코드의 비교 순서는 다음과 같습니다.

이 경우에 배열 길이가 n이라면 총 n² 번 비교를 하게 됩니다. 그런데.. 잘 생각해보면 모든 쌍에 대해서 비교를 수행하지 않아도 됩니다.
예를 들어 i = "119"와 j = "1291"을 비교한 후에 접두어가 아닌 경우 i = "119"와 j = "2345"를 비교할 필요가 있을까요? 배열이 사전순으로 정렬되어 있기 때문에, "1291"뒤에는 "119"로 시작하는 문자열이 올 수 없습니다(사전순 정렬의 의미에 따라 "119"로 시작하는 문자열끼리 뭉쳐있을 것이라고 생각해보면 됩니다). 따라서 j = "1291"이후의 문자열에 "119"로 시작하는 문자열은 없으므로, i = "119"와 비교하는 부분은 불필요한 연산이 되지요.

따라서, "119"가 "1291"의 접두어가 아니라면, 남아있는 비교 연산을 수행하지 않고 그냥 i = "1291"과 j = "2345"를 비교하는 부분으로 건너뛰어도 됩니다(i = "1291"과 j = "119"를 비교하지 않아도 되는 이유 역시 마찬가지로, 이미 이전에 비교를 했기 때문입니다. "119"와 "1291"을 비교하는 것은 "1291"과 "119"를 비교하는것과 같으니까요).

위 내용을 정리하면, 결국 문자열을 사전순으로 정렬한 경우 서로 붙어있는 문자열끼리만 비교해보면 접두어인 경우를 찾을 수 있습니다. 이 경우 붙어있는 문자열끼리만 비교하면 되므로, 전체 비교횟수는 n - 1번이 됩니다.

문자열의 개수 n = 1,000,000인 경우

• 모든 쌍에 대해 비교하는 경우의 횟수 = n² = 1,000,000² = 1,000,000,000,000 번의 연산이 필요
• 인접한 문자열끼리만 비교하는 경우의 횟수 = n - 1 = 999,999 번의 연산이 필요

1억번의 연산을 하는데 1초 정도 걸린다고 생각한다면, 위는 10,000초가 필요한 반면, 아래는 0.01초면 충분하지요

이 문제에서 실제 걸리는 시간은 문자열을 정렬하는데 필요한 시간과 문자열의 길이까지 고려해줘야 하며, 시간 복잡도는 O(nlogn)정도로 생각하면 됩니다.

답변을 적고보니 이 문제가 해시로 분류되어 있네요. 위 답변은 작성하신 코드가 시간초과 걸리는 이유와, 이를 해결하는 방법에 대한 것이고, 이번에는 해시로 푸는 방법을 적어보겠습니다.

입력이 ["119", "1291", "2345", "3456"]인 경우, 우선 각 전화번호를 다음과 같이 접두어들로 쪼개줍니다. (일단 접두어에서 자기 자신은 제외하겠습니다)

위와 같이 쪼갠 접두어들을 모두 모아 접두어 목록이라고 부르겠습니다. 이제 phone_book에 들어있는 각 전화번호가 접두어 목록에 들어있는지 확인해 보기만 하면 됩니다. 여기서 고민할 부분은 접두어 목록에 찾는 문자열이 들어있는지 어떻게 빠르게 확인할 것인가? 하는 부분입니다. 접두어 목록을 리스트 형태로 저장한다면 리스트에 해당 문자열이 들어있는지 찾기 위해 최악의 경우 리스트를 처음부터 끝까지 순서대로 하나씩 뒤져야 합니다. 하지만 해시 형태로 저장한다면 평균적으로 O(1)시간에 찾을 수 있지요. 파이썬에서는 보통 set이나 dictionary가 이에 해당합니다.

def solution(phone_book):
    s = dict()
    for p in phone_book:
        for i in range(1, len(p)):
            s[p[:i]] = 1
    # s = list(s) # 주석을 풀고 제출해보세요
    for p in phone_book:
        if p in s:
            return False
    return True

접두어 목록에서 자기자신을 제외한 이유 - 접두어 목록에 자기 자신을 포함시킬 경우 이후에 각 전화번호가 접두어 목록에 있는지 확인할 때 발견한 문자열이 자기 자신인지, 혹은 다른 문자열의 접두어인지 구분할 수 없습니다. 다른 방법을 사용해서 구분해 줄 수도 있지만, 문제에서 phone_book에 같은 전화번호가 중복해서 들어있지 않다고 했으므로, 간단하게 자기자신은 포함시켜 주지 않으면, 이후에 찾을 때 따로 구분해 주지 않아도 됩니다. 만약 접두어 목록에 찾는 전화번호가 들어있다면, 자기자신이 아니므로 무조건 다른 전화번호의 접두어가 됩니다.

• 접두어 목록의 크기가 얼마나 될지 계산해보면, 각 전화번호에서 최대 19개(자기자신 제외)의 접두어가 만들어지고, 전화번호의 개수가 1,000,000개 이므로, 접두어 목록에는 최대 19,000,000개의 문자열이 들어가게 되겠네요.
• 또, 반대로 phone_book의 번호를 모두 해시로 저장해준 후, 각 전화번호의 접두어들을 해시에서 찾는 방식으로도 풀 수 있습니다.