[프로그래머스(Python)] 전화번호 목록

문제

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 # 접두사가 맞으면 False 반환  
            
    return True # 접두사 관계 없으면 True 반환

---

해설

• 문자열 비교 특성 때문에 정렬을 통해 비슷한 문자열들이 서로 인접하도록 하면 효율적으로 탐색할 수 있다.
  • => O(n log n)
• 정렬하지 않는다면 모든 번호 쌍을 비교해야하기 때문에 효율적이지 않다.
  • => O(n^2)