[알고리즘][Python] 백준(BOJ) 5052 전화번호 목록_파이썬

 

5052 전화번호 목록    https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 트라이(Trie)

 

 

 

 

 

 

 

 

풀이 1

<내용>

• 전화번호 목록을 받아서 정렬을 하면 prefix의 가능성이 있는 번호가 앞뒤로 정렬된다.
• 따라서 바로 뒤에 있는 번호만 확인하면 된다.

 

 

 

<코드>

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    nums = [input() for _ in range(n)]
    nums.sort()
    flag = True
    for i in range(n-1):
        long = len(nums[i])
        if nums[i] == nums[i+1][:long]:
            flag = False
            break
    if flag:
        print('YES')
    else:
        print('NO')

 

 

+)  Trie를 사용해보자.

 

 

 

 

 

 

풀이 2

<내용>

• 문자열 검색할 때 특화된 Trie를 사용한다.

 

 

 

<코드>

import sys
input = sys.stdin.readline

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}
        
class Trie(object):
    def __init__(self):
        self.head = Node(None)
        
    def insert(self, string):
        curr_node = self.head
        
        for s in string:
            if s not in curr_node.children:
                curr_node.children[s] = Node(s)
            curr_node = curr_node.children[s]
        
        curr_node.data = string
        
    def search_prefix(self, string):
        curr_node = self.head
        
        for s in string:
            curr_node = curr_node.children[s]
            
        if curr_node.children:
            return False
        else:
            return True

t = int(input())
for _ in range(t):
    n = int(input())
    trie = Trie()
    nums = []
    for _ in range(n):
        num = input().rstrip()
        nums.append(num)
        trie.insert(num)
    
    flag = True
    nums.sort()
    for num in nums:
        if not trie.search_prefix(num):
            flag = False
            break
    if flag:
        print('YES')
    else:
        print('NO')

 

 

 

 

 

 

 

 

시도 1 ==> 완전 탐색은 시간 초과

<내용>

• 단순히 완전 탐색을 통해서 일관성 있는 목록인지 아닌지 찾으려 했으나 시간 초과가 발생한다.

 

 

 

 

<코드>

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    nums = [int(input()) for _ in range(n)]
    nums.sort(key=lambda x:len(str(x)))
    flag = True
    for i in range(n):
        long = len(str(nums[i]))
        for j in range(i+1, n):
            if long == len(str(nums[j])):
                continue
            if str(nums[i]) == str(nums[j])[:long]:
                flag = False
                break
        if not flag:
            break
    if flag:
        print('YES')
    else:
        print('NO')

 

 

 

 

 

 

 

 

복습

<내용>

• sys.stdin.readline()을 통해서 입력받을 때, 특히 문자열인 경우 개행 문자를 신경 쓰자!!