[Python]문자열 알고리즘1 백준 5670

   문제

   https://www.acmicpc.net/problem/5670

검색어 자동 완성에도 트라이 구조가 사용된다는걸 알수있다.

주어진 단어들을 트라이 구조에 넣은후 찾고자 하는 단어를 입력할때 다음단어가 둘

이상이거나 다른 단어의 끝이라면 추가 입력이 필요하다.

입력은 테스트 케이스의 횟수가 정해져 있지 않아서 예외처리를 해주었다.

파이썬으로 제출하여 성공할려고 하였으나 시간초과가 났다. 입출력에서 줄여야 

하는데 아직 부족한거 같다.

아래 코드는 pypy3를 통해 통과하였다.

import sys
 
class Node:
    def __init__(self,chr):
        self.chr=chr#해당 노드의 문자
        self.child={}#해당 노드의 자식들
        # self.len=0#해당 노드의 자식수
        self.check=False#문자열의 끝인지.
 
class Trie:
    def __init__(self):
        self.root=Node('')
 
    #트라이 구조 만들기
    def insert_Word(self,word):
        node = self.root
        for w in word:
            if w not in node.child:#해당노드의 자식들에 해당 문자가없다면
                #노드만들기
                new=Node(w)
                node.child[w]=new
                node=new
            else:#있다면 노드만 교체
                node=node.child[w]
        node.check=True
 
    #최소입력
    def search(self,word):
        cnt=0
        current=self.root
        for w in word:
            current=current.child[w]
            if len(current.child)>1 or current.check:#해당노드의 자식이 둘 이상이거나 다른단어의 끝이라면
                cnt+=1
        return cnt
 
while 1:
    t = Trie()
    words=[]
    #입력처리
    try:n=int(sys.stdin.readline())
    except:break
 
    for _ in range(n):
        s=sys.stdin.readline().rstrip()
        t.insert_Word(s)
        words.append(s)
    result = 0
    for word in words:
        result+=t.search(word)
 
    print("%.2f" % (result/n))