[BOJ]5052(python)

백준 5052(전화번호 목록) python 풀이입니다

Trie 구조

문자열을 Tree 형식으로 만들어 문자열 검색을 하는 구조,
가장 긴 문자열 길이(O(N)) 만큼의 시간이 소요돼서 효율적이다

어떻게 풀이

다음과 같이 문자열을 Tree 형식으로 저장한 후
다시 입력받은 문자열을 돌며 자식 노드 여부를 확인

ex 1193, 119

• 119의 경우 마지막 노드인 9 node의 자식이 존재한다
• 즉 119는 다른 문자열의 prefix이다

코드

class Node(object):
    def __init__(self) :
        self.children = {}

class Trie:
    def __init__(self):
        self.head = Node()

    def insert(self, string):
        cur = self.head

        for c in string:
            if c not in cur.children:
                cur.children[c] = Node()
            cur = cur.children[c]

    def is_prefix(self, string):
        cur = self.head

        for c in string:
            cur = cur.children[c]
        
        if not cur.children:
            return False 
        return True


def solution():
    n = int(input())
    words = []
    trie = Trie()

    for _ in range(n):
        word = input()
        words.append(word)
        trie.insert(word)

    for w in words:
        if trie.is_prefix(w):
            return "NO"
    
    return "YES"
        

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

for _ in range(t):
    answer.append(solution())

for a in answer:
    print(a)

• Node class를 정의한다
  • 각 노드는 자식 노드를 가지게 된다(중복 X)
• Trie class를 정의한다
  • 시작 노드는 아무것도 없는 노드
• insert 시 문자열을 돌면서 문자를 자식 노드에 추가
  • 해당 문자가 자식 노드로 존재하지 않으면 자식 노드를 생성
  • 자식 노드를 현재 노드로 지정
  • 위 과정을 반복
• prefix 여부를 판단한다
  • 첫번째 노드는 문자열의 첫번째 문자에 해당되는 노드
  • 자식 노드 중 두번째 문자열의 노드를 찾음
  • 그 자식 노드를 현재 노드로 지정
  • 위 과정을 반복하여 문자열의 마지막 단어 노드까지 진행
  • 마지막 단어 노드에 자식 노드가 있다면, 그 문자열은 다른 문자열의 prefix에 해당된다

---

참고
https://m.blog.naver.com/cjsencks/221740232900

아이고 코로나 죽겄다..(안죽음)