[BOJ] 5670 - 휴대폰 자판 (Python)

 

 

아이디어

 

트라이를 이용하여 단어들의 공통 부분을 확인한다.

 

 

풀이

 

테스트 케이스 수가 입력으로 주어지지 않으므로 try except문으로 입력이 주어지는 동안 while문을 반복한다.

클래스로 구현한 트라이 trie를 생성하여 insert로 단어들을 트라이에 넣고, search로 결과값 res에 입력 횟수를 더한다.

 

트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다.

insert 메서드는 단어의 문자들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성하고,

단어가 끝나는 지점에서는 별 문자를 키로 빈 딕셔너리를 저장한다.

search 메서드는 문자의 문자들을 루트 노드에서부터 차례로 찾고, 유일한 문자가 아니면 입력 횟수 cnt를 1 증가시킨다.

 

결과값 res를 N으로 나눈 평균을 f-string으로 소수점 둘째 자리에서 반올림하여 출력한다.

 

import sys

input = sys.stdin.readline

class Trie:
    def __init__(self):
        self.root = dict()

    def insert(self, S):
        node = self.root
        for c in S:
            if c not in node:
                node[c] = dict()
            node = node[c]
        node['*'] = dict()

    def search(self, S):
        node = self.root[S[0]]
        cnt = 1
        for c in S[1:]:
            if len(node) > 1:
                cnt += 1
            node = node[c]
        return cnt

while 1:
    try:
        N = int(input())
        trie = Trie()
        words = [input().rstrip() for _ in range(N)]
        res = 0
        for i in range(N):
            trie.insert(words[i])
        for i in range(N):
            res += trie.search(words[i])
        print(f'{(res/N):0.2f}')
    except:
        break