Programmers - 자동완성[파이썬(python)]

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17685

코딩테스트 연습 - [3차] 자동완성

 

문제 설명

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, 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

출력 형식

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

---

문제 풀이

트라이 라는 자료구조를 몰랐을 때는 무턱대고 글자마다 검색해야 하는 글자 수를 이분 탐색을 통해 찾으려고 했었다.

조건에서 단어의 갯수가 최대 100,000개 이고 단어의 길이의 총합은 1,000,000이라 길이가 10인 문자열이 100,000개 있다고 가정해보자.

길이가 10인 단어의 최소 검색단어수를 이분 탐색으로 찾을 경우 log10은 대략 3이라고 가정하면, 하나의 단어의 최소 검색 길이를 찾기 위해 words 전체 리스트를 3번 완전 탐색해야 한다.. 이때 대략 탐색 횟수는 300,000이 된다. 이것을 words 리스트 전체에 대해 수행한다고 하였을 때 연산 횟수는 300,000 x 100,000으로 300,000,000,000회를 해야 해서 당연히 시간 초과가 떴다. 이때 시간 복잡도는 문자열의 길이를 M, words 리스트의 길이가 N이라고 했을 때

O(N x NlogM)이 된다. 문자열 각각의 길이가 짧기 때문에 이분 탐색으로 접근하면 정답을 받을 수없다.

이분 탐색 구현 코드(시간 초과)

def binary_search(current_word, words):
    start = 0
    length = len(current_word)
    end = length
    result = 0
    while start <= end:
        count = 0
        mid = int((start+end)/2)
        subset = current_word[:mid]
        for word in words:
            if subset in word:
                count += 1
        if count > 1:
            if mid == length:
                return mid
            start = mid + 1
        else:
            end = mid - 1
            result = mid
    return result

def solution(words):
    answer = 0
    for word in words:
        answer += binary_search(word, words)
    return answer

 

이 문제의 경우 트라이 자료구조를 활용하여 풀어야 하기때문에 트라이에 대해 공부하고 백준에서 3문제를 풀어보고 나서 정답을 받을 수 있었다. 트라이는 자료구조를 사용했을 때 길이가 10인 문자열이 100,000개 있다고하면 문자열의 길이를 M words 리스트의 길이를 N이라고 했을 때 트라이를 구성하는데 O(NM)의 시간 복잡도를 갖는다 대략 1,000,000번의 연산이 필요하다. 문자열 각각 마다 최소 입력 문자를 찾는데 걸리는 시간 복잡도는 O(NM)으로 이 또한 대략 1,000,000번의 연산 횟수가 필요하다 둘을 합치면 2,000,000번의 연산으로 O(2NM)의 시간 복잡도를 가지므로 시간 초과를 피해 정답을 받을 수 있다.

트라이 구현 코드(정답)

class Node(object):
    def __init__(self, key, data=0):
        self.key = key
        self.data = data
        self.children = {}

class Trie:
    # 초기화 해드를 빈 노드로 설정
    def __init__(self):
        self.head = Node(None)

    # insert함수 - 트리를 생성하기 위한 함수
    def insert(self, string, num):
        # head노드부터 시작
        current_node = self.head
        
        # 문자열의 문자를 하나씩 확인
        for char in string:
            # 현재 노드의 자식중에 문자가 없다면
            if char not in current_node.children:
                # 자식 노드 추가
                current_node.children[char] = Node(char, 1)
                current_node = current_node.children[char]
            # 자식 중에 문자가 있다면 current_node를 자식 노드로 변경
            else:
                current_node = current_node.children[char]
                current_node.data += 1
    
    def search(self, string):
        # head노드부터 시작
        current_node = self.head
        
        #문자열의 문자를 하나씩 확인
        count = 0
        for char in string:
            count += 1
            # 만약 현재 노드의 자식노드중 문자에 해당하는 노드가 존재한다면
            if char in current_node.children:
                # current_node를 자식 노드로 변경
                current_node = current_node.children[char]
                if current_node.data == 1:
                    return count
        return count
                    
def solution(words):
    trie = Trie()

    for word in words:
        trie.insert(word, 1)
    answer = 0
    for word in words:
        answer += trie.search(word)
    
    return answer

내일도 꾸준히 공부해야겠다!