[BOJ] 5052 - 전화번호 목록

이준기·2022년 3월 17일

Trie boj 알고리즘

문제 링크

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

문제 설명

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

긴급전화: 911
상근: 97 625 999
선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

문제 풀이

트라이 알고리즘을 공부하다 만난 문제이다. 하지만 트라이로 풀지 않는 방법도 있다!

정렬로 풀기

핸드폰번호들을 문자열 순서로 정렬시키면, 바로 앞뒤에 있는 번호들만으로도 접두어 판별이 가능하게 된다. (순서가 보장되기 때문)

트라이(Trie) 란?

트라이는 한 단어의 접두사(접두어)를 모두 저장하고 있는 자료구조이다. (해당 단어에 도달하기까지의 문자들을 저장한다)

트라이에 app, ant, apple란 단어들을 순서대로 저장한다 치자.

단어의 끝에는 표시가 돼있고, 루트로부터 글자를 따라가다가, 표시가 된 곳을 방문한다면, 지금까지의 자취가 곧 하나의 단어가 된다.

하지만 트라이 자료구조는 공간복잡도가 많이 나간다는 단점이 존재한다.

맞은 코드

정렬

t = int(input())

def sol(phones):
  
  for i in range(len(phones)-1):
    phoneLength = len(phones[i])
    if phones[i] == phones[i+1][:phoneLength]:
        print("NO")
        return

  print("YES")

for _ in range(t):
  phones = []
  n = int(input())
  
  for i in range(n):
    phones.append(input())

  phones.sort()
  sol(phones)

Trie

class Node:
  def __init__(self, data):
    self.data = data
    self.child = {}
    self.last = False	# 마지막 원소인지 확인

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

  def insert(self, nums):
    nowNode = self.root
    
    for num in nums:
      if num in nowNode.child:
        nowNode = nowNode.child[num]
      else:
        newNode = Node(num)
        nowNode.child[num] = newNode
        nowNode = newNode
        
    nowNode.last = True

  # 접두어인지 확인하는 메소드
  def isPrefix(self, phone):
    nowNode = self.root
    
    for num in phone:
      if nowNode.last == True:
        return False
        
      if num in nowNode.child:
        nowNode = nowNode.child[num]

    return True
        
t = int(input())

for _ in range(t):
  phones = []
  n = int(input())
  trie = Trie()
  result = 1
  
  for i in range(n):
    tmp = input()
    phones.append(tmp)
    trie.insert(tmp)

  for phone in phones:
    result *= trie.isPrefix(phone)

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