[알고리즘][Python] 백준(BOJ) 14425 문자열 집합_파이썬

 

14425 문자열 집합    https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

 

 

 

 

 

문제 풀기 전 공부할 것 : 문자열, 트리, 트리를 사용한 집합과 맵, 트라이

 

 

 

 

 

 

 

풀이 1

<내용>

Trie를 공부했으므로 Trie로 풀어보기

• Trie를 구현한다.
• 집합 S는 Trie의 insert를 이용한다.
• M개의 문자열은 search를 통해 집합 S에 포함되어 있는지 여부를 판단한다.

---

• python 시간 초과
• pypy 정답

 

 

<코드>

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}
        
class Trie(object):
    def __init__(self):
        self.root = Node(None)
        
    def insert(self, string):
        curr_node = self.root
        
        for s in string:
            if s not in curr_node.children:
                curr_node.children[s] = Node(s)
            curr_node = curr_node.children[s]
            
        curr_node.data = string
        
    def search(self, string):
        curr_node = self.root
        
        for s in string:
            if s in curr_node.children:
                curr_node = curr_node.children[s]
            else:
                return False
        if curr_node.data:
            return True
        return False
    

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
trie = Trie()
cnt = 0
for i in range(n+m):
    string = input().rstrip()
    if i < n:
        trie.insert(string)
    else:
        if trie.search(string):
            cnt += 1

print(cnt)

 

+) Python으로 통과가 될 수 있도록 Trie 말고 다른 방법으로 구현하기

 

 

 

 

 

 

 

 

풀이 2

<내용>

• Trie는 Python에서 시간 초과이므로 Trie가 아닌 다른 방법으로 풀어본다.
• N과 M의 범위가 1 이상 10,000 이하 이므로 for문을 통해 확인한다.

 

 

<코드>

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
strings = {input().rstrip() for _ in range(n)}
cnt = 0

for j in range(m):
    string = input().rstrip()
    if string in strings:
        cnt += 1
print(cnt)