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에 대해서 알아보자