[프로그래머스 코딩테스트 연습] 전화번호 목록 (Python3)

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

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

O(NlogN) 코드이다.

 

def solution(phone_book):
    phone_dict = {}  # 딕셔너리 초기화
    
    # 모든 번호를 딕셔너리에 저장
    for number in phone_book:
        phone_dict[number] = True
    
    # 각 번호의 접두사가 딕셔너리에 존재하는지 확인
    for number in phone_book:
        temp = ""  # 접두사를 저장할 임시 변수
        for char in number:  # 번호의 각 문자를 순회하며 접두사를 생성
            temp += char
            if temp in phone_dict and temp != number:  # 접두사가 딕셔너리에 존재하지만, 본인은 제외
                return False
    
    return True

O(L*N) 코드이다.

딕셔너리를 사용하면 훨씬 빠르게 조회할 수 있다.

접두사를 하나씩 체크해서 체크한다.

 

예를 들면 ["119", "97674223", "1195524421"] 에서

1. temp "1" -> "11" -> "119" 일 때, "119"는 딕셔너리에 있고, 본인이다.

2. temp "9" -> "97" -> ... "97674223" 일 때, "97674223"는 딕셔너리에 있고 본인이다.

3. temp "1" -> "11" -> "119" 일 때, "119"가 딕셔너리에 있고, 본인(number)이 아니다. 그러기에 False