이 포스팅은 프로그래머스 시리즈 28 편 중 5 번째 글 입니다.
목차
풀이
이게 보면, 전화번호 개수가 백만개라 단순히 비교로 풀면 n^2이라 박살난다. 그렇기 떄문에 다른 방법을 고민해야한다. 이 문제의 핵심은 결국 특정 단어가 접두어로 있는지에 대한 문제이다. 그렇기 때문에 startswith를 생각하는 것이 편하다. 자 그러면 시간을 어떻게 줄일까. 접두어가 존재하기 위해서는 일단 큰단어에서 작은 단어를 비교하는 것이 가능하다. 큰단어는 작은 단어의 접두어로 존재하는 것이 불가능하다. 그렇기 때문에 일단 길이를 기준으로 정렬하는 것이 좋아보인다. 그런데 그렇게 되면 문제가 생긴다. 여전히 비교하려면 n^2이다.
따라서 정렬의 순서는, 앞의 자리수에 지배적으로 정렬이 돼되, 길이가 긴 경우 나중으로 가도록 해야 한다. 즉,
12 145 1589 23 235 26 2590
이런식으로 말이다. 이렇게 되면 일단 굉장히 편한게, 앞에 두개씩만 비교를 진행하면 왼쪽 요소의 접두어 존재 여부를 한번에 해결할 수 있다. 즉, 작은 길의의 문자열이 앞으로 오게 하면서, 그 부분적으로 길이 순서대로 정렬을 하고 싶은 것. 그런데 딱 이렇게 돌아가는것이 바로 문자열 정렬이다.
Code
def solution(phone_book):
answer = True
phone_book = sorted(phone_book)
for a, b in zip(phone_book[:-1], phone_book[1:]):
if b.startswith(a):
answer = False
break
return answer