항해 TIL
def solution(phone_book):
answer = True
for i in range(len(phone_book)):
phone = phone_book[i]
p_len = len(phone)
# print(phone)
target_book = phone_book[:i] + phone_book[i+1:]
# print(target_book)
for target_phone in target_book:
target = target_phone[:p_len]
if target == phone:
# print(target)
return False
return answer
Python
복사
def solution(phone_book):
phone_book.sort(key = lambda x: len(x))
for i in range(len(phone_book)):
phone = phone_book[i]
p_len = len(phone)
# print(phone)
target_book = phone_book[i+1:]
# print(target_book)
for target_phone in target_book:
target = target_phone[:p_len]
if target == phone:
# print(target)
return False
return True
Python
복사
채점 결과
정확성: 83.3
효율성: 8.3
합계: 91.7 / 100.0
Plain Text
복사
from itertools import combinations
def solution(phone_book):
phone_book_hash = {}
for comb in combinations(phone_book, 2):
a, b = comb
len_1 = len(a)
len_2 = len(b)
if len_1 < len_2 and a == b[:len_1]:
phone_book_hash[a] = b
for elem in phone_book:
if phone_book_hash.get(elem):
return False
return True
Python
복사
오히려 더 안 좋은 풀이
정답
•
정렬 활용
◦
전화번호부를 정렬함으로써, 접두어 관계에 있는 번호들이 서로 인접
◦
문자열 정렬은 사전식 순서를 따르므로, 접두어 관계에 있는 번호들은 반드시 연속
•
인접한 번호만 비교
◦
정렬 후에는 각 번호와 바로 다음 번호만 비교
◦
이는 모든 가능한 쌍을 비교하는 것보다 훨씬 효율
•
startswith 메소드 사용
◦
Python의 startswith 메소드를 사용하여 접두어 관계를 쉽게 확인
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
------------------------------------------------------
def solution(phone_book):
phone_book.sort() # 전화번호부를 정렬합니다.
for i in range(len(phone_book) - 1):
len_1 = len(phone_book[i])
if phone_book[i+1][:len_1] == phone_book[i]:
return False
return True
Python
복사
테스트 1 〉 | 통과 (2.63ms, 10.7MB) |
테스트 2 〉 | 통과 (2.74ms, 10.8MB) |
테스트 3 〉 | 통과 (100.02ms, 30.5MB) |
테스트 4 〉 | 통과 (89.55ms, 28MB) |
해시를 이용한 방법
def solution(phone_book):
prefix_map = {}
phone_book.sort(key = lambda x: len(x))
for idx, phone_number in enumerate(phone_book):
for i in range(len(phone_number)):
prefix = phone_number[:i]
if prefix in prefix_map:
return False
if phone_number in prefix_map:
return False
prefix_map[phone_number] = phone_number
return True
Python
복사
테스트 1 〉 | 통과 (1.44ms, 10.8MB) |
테스트 2 〉 | 통과 (1.57ms, 10.8MB) |
테스트 3 〉 | 통과 (523.38ms, 46.7MB) |
테스트 4 〉 | 통과 (222.45ms, 29.4MB) |