데이터가 1,000,000개까지 가니까 최대 시간복잡도를 O(nlogn)까지 끊어야한다. => 파이썬의 정렬 사용 가능.
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 반환정렬해서 인접한 것끼리만 비교하면 된다.
내가 푼 풀이 => deque, stack 이용
from collections import deque
def solution(phone_book):
phone_book = deque(sorted(phone_book, key=lambda x : (x, len(x))))
stack = []
while phone_book:
x = phone_book.popleft()
if stack and x.startswith(stack[-1]) :
return False
stack.append(x)
return True
시간 복잡도를 줄이려고 정렬해서 덱과 스택을 사용했다. 근데 위 풀이가 더 간단하다.
문제에서 의도한 해시맵 풀이
def solution(phone_book):
# 해시맵(딕셔너리) 초기화
phone_map = {}
# 각 전화번호를 해시맵에 저장
for phone_number in phone_book:
phone_map[phone_number] = True
# 각 전화번호에 대해 접두어가 해시맵에 존재하는지 확인
for phone_number in phone_book:
prefix = ""
for digit in phone_number[:-1]: # 마지막까지 가지 않고 접두어만 확인
prefix += digit
if prefix in phone_map: # 접두어가 해시맵에 존재하면
return False # 다른 전화번호의 접두어가 된 것이므로 False 반환
return True # 접두어가 없는 경우 True 반환
