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

코드

시간 초과 코드

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

시간복잡도(big-O)에 데이터 크기(n)을 넣어서 나온 값이 100,000,000(1억)이 넘으면 시간 제한 초과할 가능성 있음 !

for문을 2번쓰면 최악의 경우 O(N^2)

1 ≤ phone_book ≤ 1000000 이므로, O(N^2)은 안됨.

 

https://thals.tistory.com/214

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

놀랍게도 이때와 같은 코드를 작성했다 ㅋ ㅋ

시간복잡도 생각하면서 문제 풀으라고 ! ! ! ! ! 

 

정답 코드

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

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

l = ['10', '1', '5']

print(sorted(l))
# ['1', '10', '5']

string의 sort 방법을 보면 숫자 자릿수