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

문제 요약

중복 없는 학습 단어들이 주어졌을 때, 각 단어를 다른 단어와 구분해 자동완성하려면 몇 글자를 입력해야 하는지 구한다.

모든 단어에 필요한 입력 글자 수의 합을 반환한다.

핵심 아이디어

단어를 사전순으로 정렬하면, 어떤 단어와 가장 긴 접두사를 공유할 수 있는 단어는 정렬된 목록에서 바로 앞 또는 바로 뒤에 있다.

따라서 현재 단어가 필요한 입력 글자 수는 다음처럼 구할 수 있다.

max(앞 단어와의 공통 접두사 길이, 뒤 단어와의 공통 접두사 길이) + 1

단, 현재 단어 자체가 다른 단어의 접두사라면 더 입력할 문자가 없으므로 단어 전체를 입력해야 한다.

required = min(len(word), longest_common_prefix + 1)

왜 인접한 단어만 비교할까?

사전순 정렬에서 같은 접두사를 가진 단어들은 항상 연속해서 모인다.

예를 들어 word와 wor...로 시작하는 단어들은 모두 한 구간에 모인다. 현재 단어와 가장 긴 접두사를 공유하는 단어는 그 구간에서 바로 앞이나 바로 뒤에 있으므로, 두 이웃만 비교하면 충분하다.

풀이 과정

1. 단어 목록을 사전순으로 정렬한다.
2. 각 단어와 앞 단어의 최장 공통 접두사 길이를 구한다.
3. 각 단어와 뒤 단어의 최장 공통 접두사 길이를 구한다.
4. 둘 중 큰 값에 1을 더한다.
5. 현재 단어 길이를 넘지 않도록 제한한 값을 답에 더한다.

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)

정리

자동완성에 필요한 글자 수는 해당 단어와 가장 비슷한 다른 단어를 구분할 수 있는 위치로 결정된다. 사전순 정렬 후 앞뒤 단어의 공통 접두사만 비교하면, 트라이 없이도 필요한 총 입력 횟수를 구할 수 있다.