[프로그래머스] 😎 자동완성 - [3차] 2018 카카오 블라인드 채용 / Python

😎 자동완성 - [3차] 2018 카카오 블라인드 채용

문제 설명

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.

효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

예를 들어, 학습된 단어들이 아래와 같을 때

• go
• gone
• guild

go를 찾을 때 go를 모두 입력해야 한다.

gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)

guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.

이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

입력 형식

학습과 검색에 사용될 중복 없는 단어 N개가 주어진다. 

모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

2 <= N <= 100,000

2 <= L <= 1,000,000

출력 형식

단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.

😃 나의 코드

def compare3(word1, target, word2):
    for i in range(1, len(target)+1):
        if i == (len(target)) :
            return len(target)
        if (target[0:i] != word1[0:i]) and (target[0:i] != word2[0:i]):
            return i
        
def compare2(word1, target):
    for i in range(1, len(target)+1):
        if i == (len(target)) :
            return len(target)
        if target[0:i] != word1[0:i]:
            return i  
 
def solution(words):
    answer = 0
    words.sort()
    for idx, word in enumerate(words):
        if idx == 0:
            answer += compare2(words[idx+1], words[idx])
        elif idx == (len(words)-1):
            answer += compare2(words[idx-1], words[idx])
        else:
            answer += compare3(words[idx-1], words[idx], words[idx+1])
    return answer

처음 짰을 때 시간 초과로 계속 통과를 못했는데, 처음 해결법은 다음과 같다.

첫 단어부터 마지막 단어까지 문자열을 자르면서 다시 전체 단어와 비교하는 식이다. 이렇게하면 시간복잡도는 O(n^2)이 된다. O(n^2)의 복잡도에서 시간 초과가 떴으니 이 시간 복잡도를 줄여야했다.

그래서 두번째 시행 전체 단어와 비교하는 시행을 전체를 사전식으로 정렬하여 좌, 우만 확인하는 방식으로 바꿨다. 이렇게 하면, 정렬하는 데 드는 시간 복잡도인 O(nlogn)가 전체 시간 복잡도가 된다 ( 전체 단어를 확인 하는 시행은 O(n)으로 O(nlogn)보다 작기 때문에 무시 ) 이런 식으로 방법만 정해져있다면 결과를 구하는 과정은 크게 어렵지 않다.

해당 문제는 [3차] 카카오 블라인드 채용 코딩 테스트에서 가장 어려웠던 문제라고 한다. 나와 같이 시간 초과으로 멘붕이 와서 그런 거라고 생각한다. 3차까지 간 사람들이 34.07%의 정답률을 보였으니 얼마나 까다로웠는 지 상상이 간다.

위에 나의 방식과 다르게 문제 자체에서 원했던 것은 트라이(Tri)라는 자료구조의 사용하여, 입력으로 주어진 단어로 트라이를 구성하여, 같은 접두어(Prefix)를 갖는 단어가 얼마나 있는 지를 효과적으로 찾는 것이다.

👀 눈여겨 볼만한 풀이

class Trie():
    def __init__(self):
        self.next = dict()
        self.value = 0
 
def solution(words):
    answer = 0
    tree = Trie()
    for word in words:
        subtree = tree
        for idx, val in enumerate(word):
            subtree.value += 1
            if val not in subtree.next:
                subtree.next[val] = Trie()
            subtree = subtree.next[val]
            if (idx == len(word) - 1):
                subtree.value += 1
 
    for word in words:
        subtree = tree
        counts = 0
        for idx, val in enumerate(word):
            if (subtree.value == 1):
                answer += counts
                break
            elif idx == len(word) - 1:
                answer += counts + 1
                break
            else:
                subtree = subtree.next[val]
                counts += 1
 
 
    return answer
 

위에 언급한 트라이 자료구조를 사용한 풀이이다.