[Python] 백준 5670번: 휴대폰 자판

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

5670번: 휴대폰 자판

 

 > 접근

기본적인 Trie 알고리즘을 구현해놓은 뒤, root부터 시작하는 탐색 함수를 응용해야 했다. 버튼을 누른 총 횟수를 리턴하는 DFS 함수를 토대로 잡았으며 여기에 세부적인 조건이 추가가 되는 식이었다.

먼저 타이핑 횟수를 추가하는 경우는 두 가지로, 단어가 끝나는 경우와 count(insert할 때마다 1씩 증가되는 Node의 멤버 변수)가 1인 경우이다. 전자의 경우에는 결과값에 타이핑 횟수를 추가해야 하지만 탐색은 계속해서 진행해야 한다.(예제 입력 1의 두번째 테스트 케이스에서 'h') 그리고 후자의 경우에는 그곳에서 탐색을 멈추고 타이핑 횟수를 추가해야 한다.(예제 입력 1의 첫번째 테스트 케이스에서 'goodbye')

다음으로 자동입력를 고려해야 한다. hell 또는 hello를 입력한다고 할 때, h만 눌러도 he까지 자동입력이 진행된다. h에서 e로 넘어갈 때 e 이외의 다른 경우의 수가 없기 때문에 자동입력을 해주는 것이며, 이 때의 특징은 h와 e의 count 값이 같다는 점이다.

 

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
                          
class Node:
  def __init__(self, c):
    self.c = c
    self.childrens = {}
    self.count = 0
    self.is_end = False

class Trie:
  def __init__(self):
    self.root = Node('R')

  def insert(self, strr):
    cur = self.root

    for c in strr:     
      # 없을 경우 새로 추가해줌
      if not cur.childrens.get(c):   
        cur.childrens[c] = Node(c)  
      
      cur = cur.childrens[c]     
      cur.count += 1

    cur.is_end = True

  def dfs(self, node, type_count):
    if node.count == 1:
      # 현재까지 입력한 횟수를 더하되 더이상 탐색을 해선 안 된다.
      return type_count

    res = 0
    if node.is_end:
      # 이 조건문을 통과했다는 것은, node.count가 1보다 크면서 이 노드가
      # 한 단어의 마지막이라는 것이므로, 횟수를 더하되 탐색은 계속한다.
      res += type_count     

    for next_node in node.childrens.values():     
      # 현재 노드의 카운트와 다음 노드의 카운트가 같다는 것은, 입력 가능한
      # 다른 문자가 없다는 것이므로 카운트하지 않는다.(자동 입력)
      if node.count == next_node.count:
        next_type_count = type_count
      else:
        next_type_count = type_count + 1

      res += self.dfs(next_node, next_type_count)

    return res

if __name__ == '__main__':
  while True:
    try:
      N = int(input())  
    except:
      break

    trie = Trie()    
    for _ in range(N):               
      trie.insert(str(input().rstrip()))

    print('%0.2f' % (trie.dfs(trie.root, 0) / N))