[백준 5670번] 휴대폰 자판 (Python3)

import sys
input = sys.stdin.readline

while True:
  try:
    N = int(input())
  except:
    break
  Dict = {i:{} for i in "abcdefghijklmnopqrstuvwxyz"}
  words = []
  for i in range(N):
    word = input().strip()
    words.append(word)
    last = Dict
    for letter in word:
      if not last.get(letter):
        last[letter] = {}
      last = last[letter]
    last[0] = {}

  cnt = 0
  for word in words:
    last = Dict
    for letter in word:
      if len(last) != 1:
        cnt += 1
      last = last[letter]
  print("{:.2f}".format(cnt/N))

Dict를 이용해서 쉽게 풀었다.

알고리즘을 요약하면

1. abcdefg~xyz를 key로 갖는 dict를 생성한다.

2. word를 입력받으면 words에 저장하고, word의 매 글자마다 dict를 생성한다. (ex. hello라는 word가 있으면, h:{e:{l:{l:{o:{}} 이런 식으로)

3. 글자의 마지막에는 key에 0을 추가한다. (ex. hello면 h:{e:{l:{l:{o:{0:{}}})

4. words의 모든 word에 대해 words의 매 글자마다 현 위치에서의 dict의 길이가 1이면 (즉 단어가 하나밖에 없으면) cnt를 그대로 두고, 아니면 cnt를 +1 해준다.

 

다른 사람들 풀이를 보니 트라이 라는 자료구조를 이용해서 푼 사람들이 많았다. 기본적인 알고리즘은 내 풀이와 비슷한 것 같은데 class를 이용한 코드가 많아보였다.

 

이 문제에 한해서는 내 풀이가 더 간결하고 좋아보이는데, 후에 어떤 식으로 응용될지 모르니, class는 한번도 쓴 적이 없는데, 이 기회에 한번 알아보는 것도 좋을 것 같다.

 

오늘의 교훈) class에 대해서 알아보자