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

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.
• 같은 전화번호가 중복해서 들어있지 않습니다.

풀이

굉장히 간단하게 풀었는데
길이로 정렬을 해서
for문을 두 번 돌려 i번째 다음 전화번호부터 쭉 뒤로 비교하였다.

def solution(phone_book):
    answer = True
    s_pb = sorted(phone_book, key=lambda x: len(x))
    for i in range(len(s_pb)):
        for j in range(i+1, len(s_pb)):
            if s_pb[i] == s_pb[j][:len(s_pb[i])]:
                return False
    return answer

결과는 효율성 테스트 3,4번이 시간 초과가 났다.

여기서 어떻게 더 단축할 수 있을까 고민하다가 다른 사람의 힌트를 보았다.
int 정렬이 아닌 str 정렬을 하면 앞에 글자 기준으로 정렬이 된다.

예를 들어
119, 215677, 13265849 를 정렬하면
119, 13265849, 215677 이 된다.

따라서 for문을 2번 돌리지 않고 바로 오른쪽 것만 비교하면 된다!

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

str 정렬.. 왜 생각 못했을까 ㅠ