휴대폰 자판

• 트라이 (Trie)를 써서 간단히 풀 수 있는 문제이다. 문제에서 요구하는 것은 각 단어마다 그 단어의 글자들 중 뒤에 오는 글자가 유일하지 않은 글자들의 갯수를 세어서 합하는 것인데, 트라이는 이것을 하기에 최적화된 구조이다 ⇒ 어떤 단어의 어떤 글자에 대해서, 그 뒤에 올 수 있는 글자가 유일한지를 체크하는 것을 O(1)에 할 수 있다.
  • 트라이를 만드는 데에는 O(l)이 든다. 모든 단어의 모든 글자에 대해서 체크를 하는 것 역시 l*O(1)=O(l)이므로, 총 O(l)에 풀린다. (l=단어의 길이 총합)
  • 이것을 구현한 것이 코드 1.
• 조금 다른 방식도 가능 하다. 모든 단어의 모든 글자에 대해서 체크하면서 갯수를 세는 방식으로는 여러 단어에 겹치는 노드들을 중복 방문해야 한다. 그 대신, 트라이의 모든 노드를 한번씩 순회하면서 체크하고, 조건을 만족시킬 경우, 그 노드를 접두어로 갖는 단어의 갯수를 더해주는 방식으로 구현할 수도 있다. 모든 노드들마다 그 노드를 접두어로 갖는 단어의 갯수들을 구하는 것은 재귀를 사용해서 O(l)에 해결된다. 그래서 이 경우도 빅오 노테이션으로는 O(l)이지만, 실제로는 l보다 적은 트라이의 노드 갯수만큼 반복하므로 좀 더 효율적일 수 있다.
  • 이것을 구현한 것이 코드 2
• 이렇게 생각하면 간단한 문제인데, 실제로 억셉트를 받기까지는 상당히 애를 먹었다. 원인은 시간초과였고, 평범한 trie 구현으로는 시간 초과를 피할수 없었기에, trie를 새로 만들었다. 자세한 내용은 트라이 (Trie) 참고
• 최종본 코드에서의 시간은 코드 1과 코드 2가 비슷한데, 겹치는 노드를 중복 방문하지 않은게 별 효과가 없나 생각할수도 있지만, 사실 시간 차이의 큰 팩터는 다른 쪽에 있다.
  • 코드 1에서는 입력받은 단어들을 리스트에 저장하고, 그것으로 트라이를 만든다. 코드 2에서는 단어를 리스트에 저장할 필요가 없어서 바로 트라이를 만든다. 이것은 예상보다 상당히 큰 시간 차이를 낸다
  • 코드 2에서는 모든 노드들마다 그 노드를 접두어로 갖는 단어의 갯수들을 구해야 하는데 이것도 시간이 꽤나 든다
• DFS방식으로 노드들을 순회하면서 카운트를 업데이트하며 재귀함수의 인자로 넘기고, 워드 노드에 도달했을때 카운트만큼 증가시키는 방식도 가능하다. 이 방식으로는 단어를 리스트에 저장할 필요도 없고, 그 노드를 접두어로 갖는 단어의 갯수들을 따로 구할 필요도 없어서, 가장 속도가 빠르지 않을까 싶다. 그러나 구현은 안했다

• 124128KB / 3872ms

"""Solution code for "BOJ 5670. 휴대폰 자판".

- Problem link: https://www.acmicpc.net/problem/5670
- Solution link: http://www.teferi.net/ps/problems/boj/5670
"""

import sys
from teflib import string


def main():
    while True:
        try:
            n = int(sys.stdin.readline())
        except ValueError:
            break
        words = [sys.stdin.readline().rstrip() for _ in range(n)]
        trie = string.Trie(words)
        input_count = 0
        for word in words:
            for node in trie.prefixes(word):
                if len(trie.children[node]) > 1 or trie.word_counts[node] > 0:
                    input_count += 1
        print(f'{input_count / n:.2f}')


if __name__ == '__main__':
    main()

• Dependency: teflib.string.Trie

• 255844KB / 3676ms

"""Solution code for "BOJ 5670. 휴대폰 자판".

- Problem link: https://www.acmicpc.net/problem/5670
- Solution link: http://www.teferi.net/ps/problems/boj/5670
"""

from teflib import string
import sys


def main():
    while True:
        try:
            n = int(sys.stdin.readline())
        except ValueError:
            break
        trie = string.Trie(sys.stdin.readline().rstrip() for _ in range(n))
        input_count = n      
        for node in trie.nodes():
            if len(trie.children[node]) > 1 or trie.word_counts[node] > 0:
                input_count += trie.get_child_count(node)
        print(f'{input_count / n:.2f}')


if __name__ == '__main__':
    main()

• Dependency: teflib.string.Trie