문제
https://www.acmicpc.net/problem/14425
1) Trie
처음 n개의 문자열을 trie에 적재한 뒤, 주어진 m개의 target 문자열들에 대해 일치하는 문자열들의 개수를 구했다.
이때, 일치하는 문자열을 구하기 위해 target의 문자 하나씩 타고 끝까지 갔을 때, * key에 저장해둔 최종 문자열과 비교하여 일치하면 카운트를 늘리도록 했다.
코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
trie = dict()
# trie에 단어 하나씩 적재
def store(word):
cur_root = trie
for c in word:
if c not in cur_root:
cur_root[c] = {}
cur_root = cur_root[c]
cur_root['*'] = word
# trie에 target 문자열 존재하는지 확인
def search(target):
cur_root = trie
for c in target:
if c not in cur_root:
return 0
cur_root = cur_root[c]
return 1 if '*' in cur_root and cur_root['*'] == target else 0
# make Trie
for _ in range(n):
store(input())
total = 0
# target search
for _ in range(m):
total += search(input())
print(total)2) 단순 Set
아마 직관적으로 떠오르는 방식일 것이다. n개의 문자열을 Set에 저장해두고 m개의 target 문자열의 포함 여부를 확인하는 방식이다.
코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
wsets = set([input() for _ in range(n)])
total = 0
for _ in range(m):
target = input()
total += int(target in wsets)
print(total)효율성 분석
위: Set
아래: Trie
이 문제 풀면서 나름의 반성을 한 게, 별 생각없이 Trie는 빠르니깐~ㅎㅎ 하고 처음에 Trie로 풀었는데, 생각지 못한 부분이 있었다.
입력 조건 상, 문자열의 길이 때문에 큰 차이가 발생한다.
최대 길이 500인 문자열들에 대해 먼저 N번(최대 10000) trie에 적재하는 과정을 거친 뒤, 또 최대 길이 500인 target 문자열 M개를 찾는 과정을 거친다고 생각하면, Trie는 문자별 접근하기 때문에 전체 시간은 O(N x k + M x k) (k: 문자열 길이), 최악의 경우 10000 x 500 + 10000 x 500 = 10000000이 걸리게 된다.
물론 통과는 되겠지만, 굳이 이렇게 풀 필요가 없다.
어차피 일치하는 문자열의 개수를 반환하는 것이기에, Set을 활용하는게 훨씬 시간, 공간적으로 효율적이다. N개 문자열을 set에 저장 + M개 문자열을 탐색하는 시간복잡도는 O(N + M) 밖에 안되기 때문이다.
