[프로그래머스] 자동완성

About this offer

문제 요약 중복 없는 학습 단어들이 주어졌을 때, 각 단어를 다른 단어와 구분해 자동완성하려면 몇 글자를 입력해야 하는지 구한다. 모든 단어에 필요한 입력 글자 수의 합을 반환한다. 핵심 아이디어 단어를 사전순으로 정렬하면, 어떤 단어와 가장 긴 접두사를 공유할 수 있는 단어는 정렬된 목록에서 바로 앞 또는 바로 뒤에 있다. 따라서 현재 단어가 필요한 입력 글자 수는 다음처럼 구할 수 있다. max(앞 단어와의 공통 접두사 길이, 뒤 단어와의 공통 접두사 길이) + 1 단, 현재 단어 자체가 다른 단어의 접두사라면 더 입력할 문자가 없으므로 단어 전체를 입력해야 한다. required = min(len(word), longest_common_prefix + 1) 왜 인접한 단어만 비교할까? 사전순 정렬에서 같은 접두사를 가진 단어들은 항상 연속해서 모인다. 예를 들어 word 와 wor... 로 시작하는 단어들은 모두 한 구간에 모인다. 현재 단어와 가장 긴 접두사를 공유하는 단어는 그 구간에서 바로 앞이나 바로 뒤에 있으므로, 두 이웃만 비교하면 충분하다. 풀이 과정 단어 목록을 사전순으로 정렬한다. 각 단어와 앞 단어의 최장 공통 접두사 길이를 구한다. 각 단어와 뒤 단어의 최장 공통 접두사 길이를 구한다. 둘 중 큰 값에 1을 더한다. 현재 단어 길이를 넘지 않도록 제한한 값을 답에 더한다. Python 코드 def common_prefix_length(first, second): limit = min(len(first), len(second)) index = 0 while index < limit and first[index] == second[index]: index += 1 return index def solution(words): words.sort() total = 0 for index, word in enumerate(words): longest_common_prefix = 0 if index > 0: longest_common_prefix = max( longest_common_prefix, common_prefix_length(word, words[index - 1]) ) if index + 1 < len(words): longest_common_prefix = max( longest_common_prefix, common_prefix_length(word, words[index + 1]) ) # word가 다른 단어의 접두사인 경우에는 단어 전체를 입력해야 한다. total += min(len(word), longest_common_prefix + 1) return total 예시 words = ["go", "gone", "guild"] 는 이미 사전순으로 정렬되어 있다. 단어 이웃 단어와의 가장 긴 공통 접두사 필요한 입력 go go (gone과 공유) 2 gone go 3 guild g 2 go 는 gone 의 접두사다. 공통 접두사 길이는 2이지만 go 뒤에 입력할 글자가 없으므로, 단어 전체인 2글자를 입력해야 한다. 총 입력 글자 수는 2 + 3 + 2 = 7 이다. 시간 복잡도 N 을 단어 개수, L 을 모든 단어 길이의 합, M 을 가장 긴 단어 길이라고 하자. 단어 정렬: 최대 O(N log N * M) 인접 단어 공통 접두사 계산: 각 단어는 앞뒤 단어와만 비교하므로 O(L) 시간 복잡도: O(N log N * M + L) 공간 복잡도: 정렬 구현을 포함해 O(N) 정리 자동완성에 필요한 글자 수는 해당 단어와 가장 비슷한 다른 단어를 구분할 수 있는 위치로 결정된다. 사전순 정렬 후 앞뒤 단어의 공통 접두사만 비교하면, 트라이 없이도 필요한 총 입력 횟수를 구할 수 있다.

Offer details

Provider

velog

Source

velog-rss

Score

54.39

Confidence

49%