백준 2179 비슷한 단어

🔗 [백준] 2179 비슷한 단어 

📌오늘의 학습 키워드

• 접두사? 접두사가 비슷해? 저번 문제랑 비슷한가? 트라이로 풀어 볼까?

✨공부한 내용 본인의 언어로 정리하기

• 모든 단어 중에서 🛎️중복을 제거하고 트라이에 넣어준다.
• 제일 긴 height를 가진 노드중에 제일 앞쪽에 위치한 단어들을 뽑아서 반환한다.

📚오늘의 회고

• 중복을 제거하지 않아서 틀렸었다.
• height가 0에서부터 시작하는 데 dfs 종료조건을 height가 1에서부터 시작한다고 착각해 잘못 설정하여 틀렸었다.

완전 탐색이 시간복잡도가 더 낮은 문제군! (내가 이상하게 풀었군..!)

 

[🤓문제 해결 코드]

N = int(input())
visited = []


class TrieNode:
    def __init__(self):
        self.count = 0
        self.children = {}


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        root = self.root

        for w in word:
            if w in root.children.keys():
                root.children[w].count += 1
            else:
                root.children[w] = TrieNode()
                root.children[w].count += 1
            root = root.children[w]


def dfs(node, height):
    global stack

    if node.count == 1:
        if height > 1:
            if prefix[1] < height:
                prefix[1] = height
                prefix[0] = stack[:-1]
        return

    for word, node in node.children.items():
        stack.append(word)
        dfs(node, height + 1)
        stack.pop()


trie = Trie()
stack = []
words = []

prefix = ["", 0]

for _ in range(N):
    word = input()
    if word not in words:
        words.append(word)
        trie.insert(word)

dfs(trie.root, 0)
answer = list(filter(lambda x: x.startswith(''.join(prefix[0])), words))

for i in range(2):
    print(answer[i])