[Python] 전화번호 목록

✏️ 문제

 

문제 파악

처음에는 in 으로 풀면 되지 않나 싶어서 했는데 역시나.. 시간 초과로 통과가 되지 않았다.

찾아보니 딕셔너리와 리스트(배열)의 in 연산 시간복잡도는 다음과 같았다.

자료구조	딕셔너리	리스트(배열)
시간복잡도	O(1) (평균), O(n) (최악)	O(n)

 

그래서 딕셔너리를 생성해 이를 in 처리해서 풀었다.

 

 

코드

• 시간 초과 코드

def solution(phone_book):
    for i in range(len(phone_book)-1):
        for j in range(i+1, len(phone_book)):
            if (phone_book[i] == phone_book[j][:len(phone_book[i])]) or (phone_book[j] in phone_book[i][:len(phone_book[j])]):
                return False

    return True

• 해결 코드

def solution(phone_book):
    phone_dict = {}
    
    for phone in phone_book:
        phone_dict[phone] = True
    
    for phone in phone_book:
        temp = ""
        for char in phone:
            temp += char

            if temp in phone_dict and temp != phone:
                return False

    return True