문제 링크

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

문제 설명

• 타이핑 할 때 자동으로 입력 가능한 글자가 있으면 자동으로 입력해주는 기능 개발
• 사전 단어 리스트가 주어짐
• 평균 타이핑 횟수 출력

풀이

• 트라이 구현
  • Node 클래스 구현 후 root 노드에 계속해서 삽입
• BFS로 탐색하면서 카운트
• 현재 루트가 아니면서, 마지막 철자가 아니면서, 자식 노드가 하나일 때 level 유지

후기

• 트라이 자료구조를 연습하기 위해 풀어봤다
• EOF도 처리해야한다

코드

import sys
from collections import deque


class Node:
    def __init__(self):
        self.data = ''
        self.end = False
        self.children = []


def solution():
    read = sys.stdin.readline
    while True:

        # 입력 받기
        try:
            n = int(read())
        except:
            break
        words = [read().rstrip() for _ in range(n)]

        # 트라이 생성
        root = Node()
        for word in words:
            insert(root, word)

        # 평균 출력
        print(get_avg(root))


def insert(root, word):
    curr = root
    i = 0
    while i < len(word):
        k = -1
        for j in range(len(curr.children)):
            child = curr.children[j]
            if child.data == word[i]:
                k = j
        if k < 0:
            new_node = Node()
            new_node.data = word[i]
            curr.children.append(new_node)
            curr = new_node
        else:
            curr = curr.children[k]
        i += 1
    curr.end = True


def get_avg(root):
    count, summ = 0, 0
    q = deque([[root, 0]])
    while q:
        curr, level = q.popleft()
        # 카운트
        if curr.end:
            count += 1
            summ += level
        # 자식 노드
        if curr.data:
            if curr.end:
                for child in curr.children:
                    q.append([child, level + 1])
            else:
                if len(curr.children) == 1:
                    q.append([curr.children[0], level])
                else:
                    for child in curr.children:
                        q.append([child, level + 1])
        else:
            for child in curr.children:
                q.append([child, level + 1])
    return format(summ / count, '.2f')


solution()