백준 5670번: 휴대폰 자판 (Trie)

문제링크:5670번: 휴대폰 자판 (acmicpc.net)

5670번: 휴대폰 자판

이 문제는 휴대폰의 자동완성 기능에 대한 문제이다. 만약 전체 단어 사전에 hello, hell, heaven 이렇게 세 단어가 있다면 우리가 h를 입력했을때 세 단어 모두 다음에 e가 오므로 he 까지 자동 완성된다. 그리고 만약 다음에 a를 치면 hea로 시작하는 단어는 heaven이므로 heaven이 완성된다. 만약 l을쳐서 hel을 완성하면 hello와 hell이 겹치는 hell까지 완성된다. 만약 여기서 o를 치면 hello가 되고 안치면 hell이 된다. 이렇게 하면 hello를 입력하는데에는 (h,l,o) 3번의 타자, hell은 (h,l) 2번, heaven은 (h,a) 2번의 타자가 필요하다.

 

만약 사전의 단어들이 N개 주어졌을 때에, 각 단어들의 타자들의 평균을 구하는 문제이다. 어제 개미굴 문제를 통해 배운 딕셔너리를 이용해 트라이 자료구조를 구현해 보았다. 

import sys

def find(cur,stops): #단어의 타자 수 찾기
    global cnt
    if '*' in cur: #끝인 단어가 있음
        if len(cur)==1:  #끝단어
            cnt+=stops
            return
        for nxt in cur.keys(): #끝인 단어, 계속되는 단어 둘 다 있음
            if nxt=='*':
                cnt+=stops
                continue
            find(cur[nxt],stops+1)
    else:
        if len(cur)==1: #다음 letter 1경우
            if cur==trie: #가장 초기의 경우
                for nxt in cur.keys():                 
                    find(cur[nxt],stops+1)
            else:
                for nxt in cur.keys():                 
                    find(cur[nxt],stops)
        elif len(cur)>1: #다음 letter 2경우 이상
            for nxt in cur.keys():
                find(cur[nxt],stops+1)
    
while 1:
    try:
        N=int(sys.stdin.readline().rstrip())
    except:
        break
    
    trie={}
    for _ in range(N): #각 단어들 트라이에 넣기
        word=sys.stdin.readline().rstrip()
        cur=trie
        for letter in word:
            if letter not in cur:
                cur[letter]=dict()
            cur=cur[letter]
        cur['*']=1

    cnt=0
    find(trie,0)
    print('%.2f'%(cnt/N))

먼저 word의 각 letter를 DFS해가며 trie에 넣었고, 만약 각 letter 조사가 끝났다면 단어가 끝났다는 것이므로 cur딕셔너리에 '*'을 추가해 주어 끝 단어가 있음을 표시하였다.

 

find()함수를 통해 재귀를 이용한 DFS를 구현해 탐색 해 가며 각 단어의 타자 수를 구했다. 여기서 cur은 현재 탐색하는 노드 딕셔너리이고, stops는 그 노드까지 가는데 멈춰서 타자를 기다린 횟수이다(타자를 친 횟수).

 

만약 현재 cur노드에 '*'가 있다면 해당 깊이 cur에서 끝단어가 존재한다는 뜻이다. 만약 len(cur)가 1이면 '*' 하나이므로 더이상 이어지는 단어가 없다는 것으므로 cnt를 올려주고 return하고, len(cur)가 1보다 크다면 이어지는 단어가 있으므로 '*'일때 cnt를 올려주고 해당 노드에서 다음 타자를 위해 멈춰야 하므로 그 외의 경우에는 stops+1 해주며 탐색을 지속한다.

 

만약 '*'이 cur노드에 없다면 len(cur)가 1이라면 바로 다음 letter로 가는 경우가 하나이므로 바로 다음으로 탐색해 준다. 여기서 만약 cur노드가 trie라면 다음 경우가 하나더라도 가장 초기에는 공백에서 입력을 기다려야 한다. 그래서 stop+1 해주며 탐색한다. 만약 len(cur)>1이라면 다음 letter로 가는 경우가 2개 이상이므로 멈추어서 타자를 기다려야 하므로 stop+1 해주며 다음 경우들을 탐색 해 준다.

 

그렇게 전체 단어들의 타자가 cnt에 저장되고 이를 N으로 나누고 소수점 2자리로 표현하면 답이 된다. round()함수를 쓰면 정수인 경우 2.00으로 표현해야 하지만 2.0으로 표현되기에 틀린다. 반드시 소수점 2자리까지 표현해야 맞는다.