[백준/Python] 2179번 비슷한 단어

📌 문제 탐색하기

• N(2 ≤ N ≤ 20,000)개의 영단어들이 주어질 때 가장 비슷한 두 단어 구하기
  • 비슷한 정도 = 두단어의 접두사 길이로 측정
  • 두 단어의 앞에서부터 M개의 글자들이 같을 때 M이 최대인 경우 구하기
  • 그런 경우가 여러 개일 경우 입력되는 순으로 제일 앞에 있는 단어
  • 영단어는 알파벳 소문자로만 이루어지며, 길이는 100자 이하

비슷한 정도를 접두사 길이로 측정한다는 것을 바탕으로, 트라이 자료구조를 사용하기로 했다. 트라이 자료구조에 단어를 순서대로 저장하면서, 현재 가장 비슷한 단어를 갱신해나가는 방법을 사용해서 문제를 해결해 보았다.

 

 📌 코드 설계하기

• class TrieNode 구현
  
  • 트라이 자료구조의 각 노드를 표현할 클래스
  • 프로퍼티
    • children: 각 노드의 하위 노드를 딕셔너리 형태로 저장
    • is_end: 문자열의 마지막 문자인지 여부를 boolean 형태로 저장
    • first_prefix_idx: 해당 노드까지의 문자열을 접두사로 갖는 최초 단어의 인덱스
• class Trie 구현
  • 프로퍼티
    • root: 루트 노드
    • similar_words_idx: 트라이에서 가장 비슷한 단어 두 개의 인덱스를 리스트로 저장
    • similarity: 트라이에서 가장 비슷한 단어 두 개의 유사도
  • 메소드
    • insert(self, word, order) : word를 트라이에 새로 추가하는 메소드
      1. 현재 단어의 트라이 객체 내의 다른 단어와 가장 높은 유사도를 저장할 cur_similarity를 0으로 초기화하고, 그 단어와 공통 접두사의 마지막 노드를 저장할 similar_node를 self.root로 초기화한다.
      2. word를 구성하는 문자 하나씩 탐색하며, 현재 노드의 하위 노드 중 해당 문자열을 키 값으로 갖는 노드가 있는지 확인
      3. 만약 1에서 해당 문자열을 키 값으로 갖는 노드가 없다면, 새로 추가해주면서 해당 노드의 first_prefix_idx 프로퍼티에 order(현재 word의 순서를 저장)
      4. 만약 2에서 해당 문자열을 키 값으로 갖는 노드가 있다면, 해당 노드까지를 공통 접두사로 갖는 단어가 있다는 것이므로 현재 단어의 cur_similarity에 1을 더하고, similar_node를 그 노드로 갱신한다.
      5. 단어 저장 완료 후, 문제 조건에 따라 현재 단어의 유사도가 트라이에 저장된 유사도와 같으면, 입력 순서(first_prefix_idx 활용)를 비교해서 self.similarity와 self.similar_words_idx를 갱신하고, 현재 단어의 유사도가 트라이에 저장된 유사도보다 높으면 무조건 갱신해준다.
• 메인 로직
  1. 단어 개수 N을 입력받고 N개의 단어를 words 리스트에 저장한다.
  2. Trie의 인스턴스 trie를 생성하고, words의 요소를 하나씩 trie.insert한다.
  3. trie.similar_words_idx를 바탕으로 가장 유사한 단어 두 개를 순서대로 출력한다.

 

📌 정답 코드

import sys
input = sys.stdin.readline

class TrieNode():
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.first_prefix_idx = 0

class Trie():
    def __init__(self):
        self.root = TrieNode()
        self.similar_words_idx = (0, 1)
        self.similarity = 0
    
    def insert(self, word, order):
        node = self.root
        similar_node = self.root
        cur_similarity = 0
        
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
                node.children[char].first_prefix_idx = order
            else:
                cur_similarity += 1
                similar_node = node.children[char]
            node = node.children[char]
            
        node.is_end = True
        
        if (cur_similarity == self.similarity and self.similar_words_idx[0] > similar_node.first_prefix_idx) or cur_similarity > self.similarity:
            self.similarity = cur_similarity
            self.similar_words_idx = (similar_node.first_prefix_idx, order)
        
N = int(input())
words = [input().rstrip() for _ in range(N)]

trie = Trie()
for i in range(N):
    trie.insert(words[i], i)

print(*(words[i] for i in trie.similar_words_idx), sep="\n")