문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577
맨처음에는 조합으로 뽑아서 길이가 짧은게 긴 거의 시작인가를 검사했다 (효율성 검사 시간 초과)
문자열 길이로 정렬 후, 2중 for
문으로 검사 (효율성 검사 시간 초과)
위의 경우는 모두 O(n^2)
이다.
핵심
i
와 i+1
만 비교하면됨위와 같이 수행할 시 , O(n)
으로 수행 가능
from itertools import combinations
def solution(phone_book):
sortedPhone = sorted(phone_book)
for i in range(0, len(sortedPhone) - 1):
p1 = sortedPhone[i]
p2 = sortedPhone[i + 1]
if p2.startswith(p1):
return False
return True