[BOJ/백준] 5670 휴대폰 자판 파이썬

문제 링크 : https://www.acmicpc.net/problem/5670

5670번: 휴대폰 자판

 

문제 등급은 높지만 어렵지 않은 문제이다.

핵심은 트라이 자료구조를 사용하는 것이다.

 

현재 문자에서 이어질 다음 문자를 다 저장했다가 사용해야므로 트리구조가 떠올랐고, 그중 다음 글자를 자식 노드로 저장하는 트라이가 떠올랐다.

 

우선 입력으로 들어온 단어를 모두 트라이로 구성하자.

이때 해당 글자에서 단어가 끝난다는 표시를 해주자.

 

다음은 루트 노드의 자식 글자에서 시작해서 재귀로 탐색하면 된다.

total : 전체 입력 횟수

count : 시작 문자에서 부터 현재 문자까지 입력한 횟수

 

만약 현재 문자에서 끝이나는 단어가 있다면 total에 count를 더해주자.

 

그리고 현재 문자에서 자식 노드를 검사하자.

만약 자식 노드가 있다면

현재 문자에서 끝나는 단어가 없고 자식이 한개라면 추가 입력 없이 자동 완성 되는 문자이다.

그러므로 count를 유지한채 다음 재귀로 가자.

 

그렇지 않고 자식이 두개 이상이거나 현재 문자에서 끝나는 단어가 있다면 추가 입력이 필요한 문자이다.

그러므로 count+1 해주고 다음 재귀로 가자.

 

해당 과정을 모두 수행하면 전체 입력한 횟수가 나온다.

이것을 반올림하고 소수둘째자리까지 표시하자.

 

from sys import stdin
input = stdin.readline
class Node:
    def __init__(self,alpha):
        self.alpha = alpha
        self.child = []
        self.is_word = False

def solv():
    global total
    while True:
        total = 0
        n,words = input_data()
        if n == -1:
            break

        tri = make_tri(words)
        for start in tri.child:
            simul(start,1)
        print('%.2f'%round(total/n,2))
def simul(now,count):
    global total
    if now.is_word:
        total += count
    if now.child:
        if not now.is_word and len(now.child) == 1:
            simul(now.child[0],count)
        else:
            for nxt in now.child:
                simul(nxt,count+1)
def make_tri(words):
    tri = Node('-')
    now = tri
    for word in words:
        for alpha in word:
            now = search_child(now,alpha)
        now.is_word = True
        now = tri
    return tri
def search_child(now, target):
    for child in now.child:
        if child.alpha == target:
            return child
    node = Node(target)
    now.child.append(node)
    return node
def input_data():
    try:
        n = int(input())
        words = [input().strip() for _ in range(n)]
        return n,words
    except:
        return -1,[]
solv()