🧚‍♂️알고리즘🧚‍♂️ - 🎄 - 트라이

🎄트라이🎄

문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조

 

- 루트 노드는 공백 상태 유지

취향의 트라이

---

 🥈 실버 3

14425번: 문자열 집합

안타깝지만.. 이미 푼 문제라네..

시무룩이라네..

from sys import stdin
input = 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:
            # 자식 Node들 미생성된 문자열이면 새로 생성
            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() # 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)

갑자기 객체지향

근데 파이썬은 시간초과나고 파이파이로 해야 한다.

어렵.. 나중에 트라이 문제는 다시 풀어 보자

 

 

예전에 풀었던 거

from sys import stdin
N,M = map( int,stdin.readline().split()) 
Nlist = [ stdin.readline()[:-1] for _ in range(N)]
Mlist = [ stdin.readline()[:-1] for _ in range(M)]
result = 0

for cha in Mlist:
    if cha in Nlist:
        result += 1

print(result)

파이썬 문자열 굿

 

+ 또는 집합 자료형 set 이용하기

---

__init__

[Python] Class와 __init__ 이해

 

__main__

?