[해시 / 프로그래머스] 42577번: 전화번호 목록

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42577

 

Lv2. 문제다!

하나의 숫자가 다른 숫자의 접두어에 온다면 이 두수는 정렬했을 때 앞뒤에 위치하게 된다.

따라서 이중 for문으로 다 탐색하지 않아도 되고, 앞 뒤의 숫자만을 가지고 비교하면 된다 

 

- 정답 풀이 :

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

 

- 시도해본 풀이

정확성은 다 맞았는데, 효율성에서는 시간초과로 틀렸던 문제다

아무래도 이중 for문으로 돌아서 시간 복잡도가 커진게 원인인 것 같다 

def solution(phone_book):
    phone_book.sort()
    answer = True
    for i in range(len(phone_book)):
        n = len(phone_book[i])
        for j in range(i + 1, len(phone_book)):
            if phone_book[i] == phone_book[j][ : n]:                
                answer = False
                break
                
    return answer