문자열 집합

문제 설명

N개의 문자열로 이루어진 집합 S가 주어질 때, M개의 문자열 중 집합 S에 있는 문자는 총 몇 개인지 구하는 문제이다.

https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

난 trie 알고리즘을 연습하고 싶어서 풀었던 문제인데, 사실 굳이 trie 안 써도 되는 문제이긴한다.

문제 풀이

첫 번째 접근

trie알고리즘을 이용해서 풀었다.

trie 알고리즘이란 간단하게 말해서 문자열을 검색해주는 것인데, 나는 dic를 이용해서 그 트리를 만들었다. Trie 알고리즘에 관해서는 내가 따로 글을 쓰겠다.

 

아무튼 만들어준 trie 클래스에 값들을 넣고 1부터 m번째까지 문자열을 하나씩 받아서 만들어 놓은 trie 트리에 해당 문자열이 있으면 answer에 1을 더해줬다.

 

import sys


class trie:
    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        cur = self.root # 일단 처음 루트로 맞춰준다.
        for w in word:
            if w not in cur:
                cur[w] = {}
            cur = cur[w]
        cur['*'] = ''

    def find(self, word: str) -> bool:
        cur = self.root
        for w in word:
            if w not in cur:
                return False
            cur = cur[w]
        return '*' in cur


n, m = map(int, sys.stdin.readline().rstrip().split(" "))
t = trie()
for i in range(n):
    t.insert(sys.stdin.readline().rstrip())
answer = 0
for i in range(m):
    if t.find(sys.stdin.readline().rstrip()):
        answer += 1
print(answer)