문자열 집합
카카오 기출 중에 Trie자료구조를 활용해 풀어야하는 문제를 접했다. Trie라는 것에 대해 오늘 처음 들어봤기 때문에, 문제를 푸는것을 미루고 이에 대해 먼저 찾아봤다. 우리가 검색을 할 때 볼 수 있는 자동 완성 기능과 같이 문자열을 탐색하는데 특화되어있는 자료구조라고 한다. 각각의 노드들에 자식 노드를 저장시켜 놓고 단어를 탐색한다. 파이썬으로 구현할 때는 dictionary를 활용해 구현한다고 한다.
문제분석
n개의 문자를 입력받고, 다음으로 m개의 문자를 입력받는다. 이때 m개의 문자열 중에 n개의 문자열안에 포함된 문자열이 몇 개인지 알아내서 출력하는 문제이다. 입력범위가 크지 않기 때문에 단순히 배열을 사용해 풀어도 무난하게 통과할 수 있다. 하지만, Trie자료구조를 연습하는 것이 목적이었기 때문에 Trie자료구조를 활용해 풀어보았다. (Trie자료구조를 활용해 푼 코드는 pypy3로만 통과할 수 있었다.)
Trie 자료구조
“ab”, “abc”, “car”을 저장한다고 가정해보자.
먼저, “abc”를 살펴자.
- 첫번째 문자는 “a”이다. 초기에 trie 자료구조 내에는 아무것도 추가되어있지 않음으로 Head의 자식노드에 “a”를 추가해준다.
- “a”노드에도 현재 자식이 하나도 없음으로, “b”를 자식노드인 “a”의 자식으로 추가해준다.
- “c”도 마찬가지로 “b”의 자식노드로 추가해준다.
- “abc”라는 단어가 여기서 끝남을 알리기 위해 현재 노드에 abc라고 표시한다.
다음으로 “ab”를 추가해보자.
- 현재 Head의 자식 노드로 “a”가 이미 존재한다. 따라서 “a”노드를 추가하지 않고, 기존에 있던 “a”노드로 이동한다.
- “b”도 “a”의 자식노드로 이미 존재한다. “b”노드로 이동하자.
- 여기서 “ab”라는 단어가 끝이 남으로, 현재 노드에 ab를 표시한다.
“car”를 추가하자.
- Head의 자식 노드로, “a”만 존재하고 “c”는 존재하지 않는다. 따라서 “c”를 자식노드로 추가하자.
- “c”의 하위노드가 없음으로 마찬가지로 “a”를 추가한다. “r”에 대해서도 동일하다.
- “car”가 “r”노드에서 끝남으로 “car”를 표시해준다.
Python Dictionary를 이용한 구현 - 알파이님 블로그 참고
먼저 Node를 다음과 같이 만들어준다.
- Key에는 해당 노드의 문자가 들어가고, Child에는 자식 노드가 포함되게 된다.
- Data는 문자열이 끝나는 위치를 알려주는 역할을 한다. 예를 들어서 “car”이 “r”에서 끝날 때, “r”을 key로 가지는 노드의 data에 “car”를 입력한다.
- 해당 노드에서 끝나는 문자열이 없을 경우에는 None으로 그대로 놔둔다.
class Node(object):
def __init__(self, key, data=None):
self.key = key
self.data = data
self.children = {}
Dictionary를 이용해 Trie를 구현해보자.
class Trie(object):
def __init__(self):
self.head = Node(None)
# 문자열 삽입
def insert(self, string):
curr_node = self.head
# 삽입할 string 각각의 문자에 대해 자식 Node를 만들며 내려간다.
for char in string:
# 자식 Node들 중 같은 문자가 없으면 Node 새로 생성
if char not in curr_node.children:
curr_node.children[char] = Node(char)
# 같은 문자가 있으면 노드를 따로 생성하지 않고, 해당 노드로 이동
curr_node = curr_node.children[char]
#문자열이 끝난 지점의 노드의 data값에 해당 문자열을 입력
curr_node.data = string
# 문자열이 존재하는지 search
def search(self, string):
#가장 아래에 있는 노드에서 부터 탐색 시작
curr_node = self.head
for char in string:
if char in curr_node.children:
curr_node = curr_node.children[char]
else:
return False
#탐색이 끝난 후 해당 노드의 data값이 존재한다면
#문자가 포함되어있다는 뜻이다.
if curr_node.data != None:
return True
Example
“abc”, “ab”, “car”을 저장하는 과정을 살펴보자.
“abc”삽입
“ab”삽입
“car”삽입
“abc”라는 문자열이 속해있는지 탐색해보자.
- Head의 child에 “a”가 속해있음으로, “a”노드로 이동.
- “c”노드의 child에 “b”가 속해있음으로 “b”노드로 이동.
- “b”노드의 child에 “c”가 속해있음으로 “c”노드로 이동.
- 문자열의 탐색이 완료되었고, 현재 노드의 Data값이 존재한다. 따라서 “abc”라는 문자열이 존재한다!
“ca”라는 문자열이 속해있는지 탐색해보자.
- Head의 child에 “c”가 속해있음으로, “c”노드로 이동.
- “c”노드의 child에 “a”가 속해있음으로 “a”노드로 이동.
- 문자열의 탐색이 완료되었는데, 현재 노드의 Data값이 없음으로, “ca”라는 문자열은 존재하지 않는다.
CODE
import sys
read = sys.stdin.readline
# 아래의 Node, Trie class 구현 부분은
# [https://alpyrithm.tistory.com/74]
# 알파이님의 블로그를 토대로 작성했습니다.
class Node(object):
# trie 자료구조를 위한 node
def __init__(self, key, data=None):
self.key = key
self.data = data
# dictionary 자료구조 사용
self.children = {}
class Trie(object):
def __init__(self):
self.head = Node(None)
# 문자열 삽입
def insert(self, string):
curr_node = self.head
# 삽입할 string 각각의 문자에 대해 자식 Node를 만들며 내려간다.
for char in string:
# 자식 Node들 중 같은 문자가 없으면 Node 새로 생성
if char not in curr_node.children:
curr_node.children[char] = Node(char)
# 같은 문자가 있으면 해당 노드로 이동
curr_node = curr_node.children[char]
curr_node.data = string
# 문자열이 존재하는지 search
def search(self, string):
curr_node = self.head
for char in string:
if char in curr_node.children:
curr_node = curr_node.children[char]
else:
return False
if curr_node.data != None:
return True
n, m = map(int, read().split())
word_trie = Trie()
word_len = list(False for _ in range(501))
# 주어진 문자열과 길이가 같은 문자열에 대해서만 탐색을 진행해
# 시간복잡도 줄이기 위함
for _ in range(n):
word = read().strip()
word_trie.insert(word)
word_len[len(word)] = True
cnt = 0
for _ in range(m):
word = read().strip()
if word_len[len(word)] and word_trie.search(word):
cnt += 1
print(cnt)
틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍
[꼭 다시 풀어보기]