069 문자열 집합 (미해결)

첫번째 코드

 

트라이 함수를 이용해서 문자를 정렬하면서 찾아가는 방법을 이용한다.

코드는 책을 참고했다.

 

트라이라는 개념은 이해하겠으나 트리와 관련해서 코드를 작성하는 것이 너무 어렵다.

트리는 많이 보이는 문제인데....

 

import sys
input = sys.stdin.readline

class Node(object):
    def __init__(self, isEnd):
        self.isEnd = isEnd
        self.childNode = {}

class Trie(object):
    def __init__(self):
        self.parent = Node(None)

    def insert(self, string):
        nowNode = self.parent
        temp_length = 0
        for char in string:
            if char not in nowNode.childNode:
                nowNode.childNode[char] = Node(char)
            nowNode = nowNode.childNode[char]
            temp_length += 1
            if temp_length == len(string):
                nowNode.isEnd = True
    
    def search(self, string):
        nowNode = self.parent
        temp_length = 0
        for char in string:
            if char in nowNode.childNode:
                nowNode = nowNode.childNode[char]
                temp_length += 1
                if temp_length == len(string) and nowNode.isEnd == True:
                    return True
                else:
                    return False
            return False

n, m = map(int, input().split())
myTrie = Trie()

for _ in range(n):
    word = input().strip()
    myTrie.insert(word)

result = 0

for _ in range(m):
    word = input().strip()
    if myTrie.search(word):
        result += 1

print(result)

 

오류!

---

두번째 코드

 

insert나 search에서 문제가 생긴 것 같지만 확인이 되지 않아 GPT와 논의 후 코드를 다시 작성했다.

 

import sys
input = sys.stdin.readline

class Node(object):
    def __init__(self):
        self.isEnd = False
        self.childNode = {}

class Trie(object):
    def __init__(self):
        self.parent = Node()

    def insert(self, string):
        nowNode = self.parent
        for char in string:
            if char not in nowNode.childNode:
                nowNode.childNode[char] = Node()
            nowNode = nowNode.childNode[char]
        nowNode.isEnd = True
    
    def search(self, string):
        nowNode = self.parent
        for char in string:
            if char in nowNode.childNode:
                nowNode = nowNode.childNode[char]
            else:
                return False
        return nowNode.isEnd

n, m = map(int, input().split())
myTrie = Trie()

for _ in range(n):
    word = input().strip()
    myTrie.insert(word)

result = 0

for _ in range(m):
    word = input().strip()
    if myTrie.search(word):
        result += 1

print(result)

 

오류!

테스트의 경우 답은 나오지만 시간 초과의 문제가 발생한다.

---

링크