백준 5670 - 휴대폰 자판 (Python)

자식이 2개 이상이거나 단어의 끝글자일 때 1을 더해줍니다.

핵심코드

if len(node.children) > 1 or node.flag:
    cnt += 1

Trie자료구조를 사용하시면 됩니다.

전체 코드

import sys

input = sys.stdin.readline

class Node():
    def __init__(self, key):
        self.key = key
        self.children = {}
        self.flag = False
        
class Trie():
    def __init__(self):
        self.head = Node(None)
        
    def insert(self, string):
        node = self.head
        
        for char in string:
            if char not in node.children:
                node.children[char] = Node(char)
                
            node = node.children[char]

        node.flag = True
    
    def find(self, string):
        node = self.head
        cnt = 0
        
        for char in string:
            node = node.children[char]
            if len(node.children) > 1 or node.flag:
                cnt += 1

        return cnt

while True:
    try:
        n = int(input())
        a = [input().rstrip() for _ in range(n)]

        trie = Trie()

        for i in a:
            trie.insert(i)

        answer = 0
        
        for i in a:
            answer += trie.find(i)

        print('%.2f' % (answer / n))
    except:
        break