전화번호 목록

• 정해는 트라이 (Trie)를 사용하는 것.
• 트라이에 단어(=전화번호)들을 모두 저장하고, 각 단어의 노드들에 대해서 자식 노드가 있는지를 확인하면, 트라이 구축에 O(nl), 각 단어 노드를 찾고 자식을 확인하는데에 O(nl)로 총 O(nl)에 풀린다
  • 트라이의 구현을 조금 고치면, 트라이에 단어를 추가하면서 바로 접두사 케이스를 찾아낼수도 있다.
• 그러나, 트라이 (Trie)에 언급했듯이 트라이를 사용하지 않고 푸는 것이 실제로는 더 빠르다.
• 가능한 첫번째 방법은, 그냥 모든 단어를 트라이가 아닌 기본 딕셔너리에 저장하는 것이다. 그리고 각 단어에 대해서 길이 1~l까지의 모든 접두사들중에 딕셔너리에 포함된 것이 있는지를 체크하는 것이다. 이것도 딕셔너리 구축에 O(nl). 그리고 각 단어마다 O(l)개의 접두사를 비교해야 하고, 각 접두사에 대해서 해시를 계산하는 것이 O(l)일테니, 비교부분은 O(nl^2)이 된다. 총 O(nl^2)이지만 실행시간은 더 빠르다.
  • 내장된 기본 해시펑션을 쓰지 않고, 라빈 핑거프린트와 같은 incremental 한 해시 펑션을 쓰면 l개의 접두사의 해시를 각각 구하는 것을 O(l^2)이 아닌 O(l)로 줄일수가 있다. 총 시간복잡도를 O(nl)로 줄일수 있지만, 실제 실행시간은 더 느려졌다.
• 다른 방법은 단어들을 정렬한 뒤, 모든 단어에 대해서 그 단어가 바로 뒤의 단어의 접두사인지만 확인하는 것으로도 풀 수 있다, 이 경우에는 정렬 O(lnlogn) + 접두사 체크 O(nl)이지만, 실제 실행 속도는 이쪽이 가장 빨랐다.

• 69484KB / 3304ms

"""Solution code for "BOJ 5052. 전화번호 목록".

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


import sys
from teflib import string


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        trie = string.Trie(sys.stdin.readline().rstrip() for _ in range(n))
        if any(word_node.child_count > 0 for word_node in trie.words()):
            print('NO')
        else:
            print('YES')


if __name__ == '__main__':
    main()

• Dependency: teflib.string.Trie

• 31244KB / 440ms

"""Solution code for "BOJ 5052. 전화번호 목록".

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

import sys


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        words = set(sys.stdin.readline().rstrip() for _ in range(n))
        for w in words:
            if any(w[:i] in words for i in range(1, len(w))):
                print('NO')
                break
        else:
            print('YES')
            

if __name__ == '__main__':
    main()

• 30096KB / 188ms

"""Solution code for "BOJ 5052. 전화번호 목록".

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


import sys


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        words = sorted(sys.stdin.readline().rstrip() for _ in range(n))
        print('NO' if any(y.startswith(x) for x, y in zip(words, words[1:]))
              else 'YES')

        
if __name__ == '__main__':
    main()