오늘의 프로그래머스 두번째 문제

프로그래머스 - 자동완성 링크
(2022.10.24 기준 Level 4)
(치팅하면 속상해)

문제

단어 목록 중 어떤 단어를 검색하기 위해서 다른 단어들과 앞부분이 같은 경우가 없을 때까지 문자를 입력하면 자동완성이 된다.
그렇다면 모든 단어들을 찾을 때 총 몇 글자를 입력해야 하는지 출력

알고리즘

누가 봐도 전형적인 트라이 문제다. 그런데 난 트라이를 아직 공부를 안했다.
하지만 다른 방법도 있었으니.. 바로 정렬

풀이

이 문제는 단어들이 다른 단어들과 얼마나 앞부분이 같은지 계산하는 문제다.
그렇다면 간단하다.
사전순으로 정렬을 해보자. 그러면 각 단어는 인접한 두 단어씩 있는데 (양 끝은 한 단어씩), 인접한 두 단어 중 하나가 앞부분이 제일 많이 일치하는 단어이다.
그러면 인접한 단어끼리 일치하는 문자 수를 체크하면 되는데, 체크한 수는 2개가 나오니깐 그 중 최댓값이 그 단어를 검색하기 위한 입력하는 문자 수라고 보면 된다.

예제 3번째를 살펴보자.
['word', 'war', 'warrior', 'world']는 정렬하면 ['war', 'warrior', 'word', 'world']이 된다.
인접한 두 단어끼리 비교하면
war는 뒷 단어와 전부 일치한다. 일치하는 수보다 하나 더 입력해야 하지만 war는 길이가 3이므로 w, a, r 세 문자만 입력하면 된다.
warrior는 앞 단어와는 3개, 뒷 단어와는 1개 일치한다. 그러므로 max(3 + 1, 1 + 1) = 4.
word는 앞 단어와는 1개, 뒷 단어와는 3개 일치한다. 그러므로 max(1 + 1, 3 + 1) = 4.
world는 앞 단어와 3개 일치한다. 그러므로 3 + 1 = 4.
그래서 답이 3 + 4 + 4 + 4 = 15가 되는 것이다.

위 TC의 war의 경우도 생각하여 식을 세워보면
i번째 단어 words[i]의 입력해야 하는 문자 수를 result[i]라 하면
result[i] = max(result[i], min(len(words[i]), 일치하는 최대 인덱스 + 2))

이렇게 전부 구해서 합한 값을 반환하면 된다.

코드

def solution(words):
    N = len(words)
    words.sort() # 단어를 사전순으로 정렬
    result = [0] * N # 단어마다 입력해야 하는 문자 수

    for i in range(N - 1):
        # 인접하는 두 단어 비교
        a = len(words[i])
        b = len(words[i + 1])
        for j in range(min(a, b)):
            if words[i][j] != words[i + 1][j]:
                j -= 1 # 일치하지 않으면 일치하는 최대 인덱스로 저장 후 break
                break

        # 일치하는 인덱스 + 1만큼 문자를 입력해야 한다.
        # 단, 입력하는 문자 수가 단어 길이를 넘지 말아야 한다.
        result[i] = max(result[i], min(a, j + 2))
        result[i + 1] = max(result[i + 1], min(b, j + 2))

    # 단어마다 입력해야 하는 문자 수를 합해서 반환
    return sum(result)

여담

트라이를 얼른 공부해야 하는데.. 귀찮다. 아직 트라이를 꼭 공부해야겠단 동기가 없었다. 뭐 언젠간 하겠지..?