[14425] 문자열 집합 (트라이, Trie)

14425번: 문자열 집합

 

 

트라이

• 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조
• 특징
  • N진트리 : 문자 종류의 개수에 따라 N이 결정됨. 예를 들어 알파벳은 26개의 문자로 이뤄져있으므로 26진트리로 구성됨.
  • 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지
• 시간복잡도
  • 문자열의 길이가 m이라면 시간 복잡도는 O(m)
  • 현재 노드의 위치를 i, j번째 문자라고 한다면 trie[i][j]의 위치를 조회하는 건 O(1)에 수행 가능
  • 문자열의 길이만큼, 즉 m번을 수행하니 O(m)의 시간 소요

 

 

풀이

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
                # 마지막 문자까지 모두 존재하고 마지막 문자에 isEnd가 True인 경우
                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)   # 단어 삽입

# 문자열 찾기
cnt=0
for _ in range(m):
    word=input().strip()
    if myTrie.search(word):  # 단어찾기
        cnt+=1

print(cnt)

 

 

[14425] 문자열 집합 (set)

 

참고

트라이(Trie) 자료구조