[Python] 백준 5052 - 전화번호 목록 문제 풀이

Overview

BOJ 5052번 전화번호 목록 Python 문제 풀이
분류: Trie (트라이), String (문자열)

---

문제 페이지

https://www.acmicpc.net/problem/5052

---

풀이 코드 1 - 트라이

from sys import stdin
from collections import defaultdict


class TrieNode:
    def __init__(self):
        self.end = False
        self.cnt = 0
        self.children = defaultdict(TrieNode)


class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.consistency = True

    def insert(self, tel: str) -> None:
        if not self.consistency:
            return

        node = self.root
        for char in tel:
            if not char.isdigit():
                continue

            node = node.children[char]
            node.cnt += 1

            if node.end:
                self.consistency = False
                return

        node.end = True
        if node.cnt > 1:
            self.consistency = False

    def check_consistency(self) -> bool:
        return self.consistency


def main():
    def input():
        return stdin.readline().rstrip()

    t = int(input())
    for _ in range(t):
        n = int(input())
        trie = Trie()
        for _ in range(n):
            tel = input()
            trie.insert(tel)
        print(['NO', 'YES'][trie.check_consistency()])


if __name__ == "__main__":
    main()

Trie 자료구조를 구현하여 풀이하였다. 트라이에 전화 번호를 삽입할 때, 불일관성이 발견되면 self.consistency 변수를 False로 업데이트하고, 이후에는 전화 번호를 입력 받아도 트리에 삽입하지 않는다. 그리고 마지막에는 일관성 여부를 출력한다.

주의할 점은 전화 번호를 입력 받을 때는 문자열로 입력 받아야 하며, 전화 번호에 숫자가 아닌 문자가 섞여 있을 수 있다는 것이다 (예. 12-345). 따라서 숫자가 아닌 값은 트라이에 넣지 말아야 한다.

---

풀이 코드 2 - 문자열 슬라이싱

from sys import stdin
from re import sub


def main():
    def input():
        return stdin.readline().rstrip()

    t = int(input())
    for _ in range(t):
        n = int(input())
        tels = [sub('[^0-9]', '', input()) for _ in range(n)]
        tels.sort()
        res = True
        for i in range(1, n):
            if tels[i - 1] == tels[i][:len(tels[i - 1])]:
                res = False
                break
        print(['NO', 'YES'][res])


if __name__ == "__main__":
    main()

입력 받은 전화 번호들을 정렬하고, 인접한 번호 끼리 비교해가며 일관성 여부를 체크한다.

두 번째 풀이가 첫 번째 풀이 보다 속도가 빠르다.