[알고리즘] 백준 5052 전화번호 목록 파이썬

문제

분류

트라이 알고리즘을 찾다가 알게 된 문제지만 트라이를 쓰지 않고 쉽게 해결하는 방법이 있어 쉬운 풀이, 트라이 풀이 둘 다 정리할 예정이다. 참고로 프로그래머스에도 전화번호 목록이라는 아주 비슷한 문제가 있다.

쉬운 풀이

'''
Problem Solving Baekjoon 5052_3
Author: Injun Son
Date: December 9, 2020
'''
import sys
import math

def solution(numbers):
    numbers.sort()
    for i in range(len(numbers) - 1): #정렬되어 있으므로 i번째는 i+1번째와만 비교해보면 된다
        if numbers[i] in numbers[i+1][0:len(numbers[i])]:
            print("NO")
            return False
    print("YES")
    return True


numbers = []
t = int(input())

for _ in range(t):
    n = int(input())
    for _ in range(n):
        numbers.append(input())
    solution(numbers)
    numbers.clear()

트라이 (Trie)

트라이 알고리즘.

제일 긴 문자열의 길이를 L, 총 문자열들의 수를 M이라 할 때
생성시 시간 복잡도 : O(M*L)
삽입 시간 복잡도 : O(L)
탐색시 시간 복잡도 : O(L)

import sys
import math


class Node:
    def __init__(self, data):
        self.data = data
        self.child = [None for _ in range(10)]
        self.check = False #해당 노드를 마지막으로 끝나는 문자열이 있는지


class Trie:
    def __init__(self):
        self.root = Node('')

    def insert(self, phone):
        tmp = self.root
        for i in phone:
            if tmp.child[i] != None:  # 비어있지 않으면
                tmp = tmp.child[i]
            else:
                new = Node(i)
                tmp.child[i] = new
                tmp = new
        tmp.check = True

    def consistency(self, phone):
        tmp = self.root
        for i in range(len(phone)):
            if tmp.check:  # 다른 문자열을 포함하고 있다면
                return False
            tmp = tmp.child[phone[i]]
        return True


for _ in range(int(input())):
    n = int(input())
    phone_list = []
    trie = Trie()

    for _ in range(n):
        phone = list(map(int, input().split()))
        trie.insert(phone)
        phone_list.append(phone)
    result = True

    for p in phone_list:
        result *= trie.consistency(p)

    if result:
        print("YES")
    else:
        print("NO")

해쉬맵(딕셔너리)을 이용한 풀이

비슷한 프로그래머스 문제.

def solution(phone_book):
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                return False
    return True