(C++) 문자열 집합 : 트라이 자료구조
카테고리: Algorithm
태그: Coding Test Cpp Algorithm
🚀 트라이 자료구조
“접두사”를 검색하거나 “단어 자체”를 검색하는 데에 특화된 문자열 집합 자료구조
여러 문자열들이 모인 집합 내에서 특정 문자열을 탐색(검색) 하고자 할 때 특화된 문자열 집합 자료구조이며 트리 형태이다. 위와 같이 문자열 집합 내에서 중복되는 "접두사"들에 대응되는 노드들이 서로 연결된 트리이다.
같은 접두사는 같은 노드로 겹쳐서 저장된다(트리라서)는 특성 때문에 접두사나 완전한 문자열을 빠르게 찾기에도 좋으며 이 특성 때문에 어떤 문자열 원소의 끝을 알리는 표시를 해주기도 한다. 보통 노드에 bool isEnd 이런 변수를 두고 어떤 문자열의 끝이라면 True 로 변경하는 식으로 한다. 위 그림에서 노란색 노드들이 문자열 끝을 의미한다!
이진 검색 트리(Binary Search Tree)도 검색을 O(logN) 만에 이루어지게 하는 효율적인 자료구조이다. 그러나 검색하고자 하는 원소가 “문자열”일 땐 문자열들을 노드로 저장한 문자열 집합 이진 검색 트리에서 검색 하더라도, 문자열 하나를 비교하는데에 문자 하나 하나를 다 크기 비교해야 하는 과정이 필요하므로, 문자열의 길이가 M 이라고 하면 최악의 경우 O(MlogN) 만큼의 시간이 소요 된다.
그러나 위 그림과 같은 트라이(Trie) 형식의 트리에 문자열 집합을 저장하면, 여기에서 원하는 문자열을 검색할 때 O(M) 딱 검색하고자 하는 문자열의 길이에 해당하는 시간만 소요 되기 때문에 매우 효율적이다.
이와 같은 일이 가능한 이유는 위 그림과 같이 문자열 집합내에서 같은 접두사를 가진 문자열들은 같은 간선에서 뻗어나가기 때문이다. 즉, 같은 부모 노드를 가진다. 위 그림에서 his 를 검색한다면, her과 his 둘 다 각각 대조해 볼 필요 없이 자연스럽게 h 👉 i 👉 s 이렇게 노드를 타고 내려오면 된다.
그렇기 때문에 자식 노드들은 곧 다음 글자와도 같다. 효율적인 시간을 위하여 자식 노드 링크를 찾는 일은 O(1) 만에 이루어지는 것이 좋다. 그래서 알파벳만을 사용하는 문자열 집합이라면 자식 노드 링크를 26 개 담을 수 있는 “배열”을 선언해 관리하기도 하고, 숫자만 사용되는 문자열 집합이라면 10 개의 배열을 만들 수도 있을 것이다. 이렇게 배열 뿐 만이 아닌, 다음 글자를 Key 로하고 그에 대응되는 노드의 주소로 연결되는 O(1) 검색 속도를 자랑하는 “해시맵”을 사용하여 자식 노드 링크들을 관리할 수도 있을 것이다. (개인적으로 디버깅시엔 해시맵이 유용한 듯 하다.)
Trie* children[26]; // 배열
unordered_map<string, Trie*> children; // 해시맵
- 루트 노드는 항상 길이 0 인 문자열에 대응된다.
- (루트 노드는 대응되는 문자가 없는 상태이다. 루트의 자식부터 첫 문자에 대응)
- 깊이가 깊어질 때마다 대응되는 문자열의 길이는 1 씩 늘어난다.
트라이의 중요한 속성은 루트에서 한 노드가지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 "접두사"를 얻을 수 있다는 것을 기억하자!
자동 완성(접두사와 관련)을 한다던가 하는 문자열 처리 프로그램을 구현할 때 유용하다. 검색 엔진에서도 많이 쓰인다.
🔥 형태와 코드
- 노드 1 개가 가지고 있어야 하는 멤버 필드
- 필수
- 자식 노드들의 링크들
- 정적 배열 혹은 해시맵으로 관리 👉 O(1) 으로 바로 탐색이 가능한
- 자식 노드들의 링크들
- 문제에 따라 선택
- 종료 노드인지를 나타내는
bool변수
- 종료 노드인지를 나타내는
- 필수
- 멤버 함수
- 삽입 👉 문자열 원소 하나 하나를 추가하며 트라이를 구성한다.
- 탐색 👉 트라이를 탐색하며 원하는 문자열 혹은 접두사 검색
#include <bits/stdc++.h>
using namespace std;
const int NUM_ALPHABETS = 26;
int toIndex(char ch) { return ch - 'a'; }
struct TrieNode {
TrieNode* children[NUM_ALPHABETS];
// unordered_map<string, TrieNode*> children;
bool isEnd;
TrieNode() : children(), isEnd(false) {}
void Insert(string& key, int index) {
if (index == key.length() - 1)
isEnd = true;
else {
int next = toIndex(key[index]);
if (children[next] == nullptr)
children[next] = new TrieNode;
children[next]->Insert(key, index + 1);
}
}
bool Find_1(string& key, int depth) { // 접두사로서 검색 되더라도 true 를 리턴하게끔 한 함수
if (depth == key.length() - 1)
return true;
int next = toIndex(key[depth]);
if (children[next] == nullptr)
return false;
return children[next]->Find_1(key, depth + 1);
}
bool Find_2(string& key, int depth) { // 완전히 일치하는 단어 단위로만 찾고 true 를 리턴하게끔 한 함수
if (depth == key.length() - 1 && isEnd)
return true;
if (depth == key.length() - 1 && !isEnd)
return false;
int next = toIndex(key[depth]);
if (children[next] == nullptr)
return false;
return children[next]->Find_2(key, depth + 1);
}
};
int main() {
vector<string> words = { "what", "when", "yours", "apple", "her", "his", "you" };
TrieNode root;
for (string word : words)
root.Insert(word, 0);
string search = "wh";
if (root.Find_1(search, 0)) cout << search << "가 검색 결과에 있습니다." << '\n';
else cout << search << "가 검색 결과에 없습니다." << '\n';
if (root.Find_2(search, 0)) cout << search << "가 검색 결과에 있습니다." << '\n';
else cout << search << "가 검색 결과에 없습니다." << '\n';
}
💎출력💎
wh가 검색 결과에 있습니다.
wh가 검색 결과에 없습니다.
🚀 트라이를 사용한 예제 문제들
1️⃣ 전화번호 목록 (백준 5052)
문제와 더 자세한 설명은 링크 참고 [백준 5052][💛4] 전화번호 목록 (해시, 트라이)
코드 펼쳐서 보기 (Click)
#include <bits/stdc++.h>
using namespace std;
class Trie {
private :
bool isEnd = false; // 이 Trie 노드 객체가 문자열(단어)의 끝인지를 알 수 있는
Trie* child[10]; // Trie 객체들은 각각 서브 트리들의 루트 노드가 된다. 자식 10 개( 0 ~ 9 )를 담을 수 있는 배열을 가지고 있음 (배열말고 해시로 해도 된다.)
public :
Trie() : child() { }
/* 트라이 트리 만들기 */
void Insert(string phone_number) {
Trie* now = this; // 루트에서부터 시작 (루트 Trie 객체에서만 이 Insert 를 한번 실행하도록 함. 재귀 안 쓰고 반복문 써서..)
for (int i = 0; i < phone_number.length(); ++i) {
if (now->child[phone_number[i] - '0'] == nullptr)
now->child[phone_number[i] - '0'] = new Trie(); // 해당 글자 자식이 없다면 Trie 객체 만들어주기. 이미 있다면 만들어줄 필요 없음.
// 다음 글자 노드로 이동 (트리 타고 내려감)
now = now->child[phone_number[i] - '0'];
// 문자열의 끝에 도달했다면 해당 글자 노드의 isEnd 를 True 로
if (i == phone_number.length() - 1) now->isEnd = true;
}
}
/* 트라이 트리에 phone_number 문자열을 타고 내려가되 중간에 isEnd 가 True 인 노드를 만나면 접두어가 있다고 판단함 */
bool IsTherePrefix(string phone_number) {
Trie* now = this; // 루트에서부터 시작 (루트 Trie 객체에서만 이 IsTherePrefix 를 한번 실행하도록 함. 재귀 안 쓰고 반복문 써서..)
for (int i = 0; i < phone_number.length(); ++i) {
if (now->child[phone_number[i] - '0'] != nullptr) {
now = now->child[phone_number[i] - '0']; // 다음 글자 노드로 이동 (트리 타고 내려감)
if (now->isEnd) // 다음 글자가 있는 상태인데(위 if) isEnd 가 True 인 경우를 만났다는 것은 이 글자가 끝인 다른 단어가 있다는 것. 접두어!
return true;
}
else // 다음 글자도 없다면(문자열 끝에 도달) 한번도 접두어가 없었던 것! (같은 문자열이 중복으로 주어지는 경우는 없다고 제한했으니 같은 문자열 접두사 있을 걱정은 안해도 되므로 그냥 더 이상 자식 없을 때까지 걸린적 없으면 접두사 없는 것임)
return false;
}
return false;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t, n;
cin >> t;
for (int i = 0; i < t; ++i) {
cin >> n;
vector<string> phone_number_list(n);
for (int j = 0; j < n; ++j)
cin >> phone_number_list[j];
sort(phone_number_list.begin(), phone_number_list.end()); // 정렬
Trie* trie = new Trie(); // 트라이 트리의 루트
bool ok = true;
for(auto phone_number : phone_number_list) {
if (trie->IsTherePrefix(phone_number)) { // 접두사 있는지 검사
ok = false;
break;
}
trie->Insert(phone_number); // 접두사 없으면 추가
}
if (ok) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
}
문자열을 트라이에서 순회하며 내려오면서 문자열의 끝에 도달하기 전에 또 다른 문자열의 끝을 만나게 된다면 트라이에 저장된 다른 문자열이 현재 검사하는 이 문자열의 접두사가 된다는 이야기이다. 이런식으로 트라이에서 자신의 접두사가 있는지 없는지를 검사하면 되는 문제였다.
2️⃣ 개미굴 (백준 14725)
문제와 더 자세한 설명은 링크 참고 [백준 14725][💛2] 개미굴 (트라이)
코드 펼쳐서 보기 (Click)
#include <bits/stdc++.h>
using namespace std;
class AntDen {
private:
map<string, AntDen*> child; // key : 자식 문자열(다음 문자열) valuse : 자식 객체 주소
public:
/* 트라이 트리 만들기 (재귀로 구현) */
void Insert(vector<string>& foods, int index) {
if (index == foods.size())
return;
if (child.find(foods[index]) == child.end())
child[foods[index]] = new AntDen();
child[foods[index]]->Insert(foods, index + 1);
}
void Output(int depth) { // DFS
for (auto& ch : child) {
for (int i = 0; i < depth; ++i) // 깊이 당 -- 한 번
cout << "--";
cout << ch.first << '\n';
ch.second->Output(depth + 1);
}
}
};
int main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
AntDen* root = new AntDen();
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
vector<string> foods(k);
for (int j = 0; j < k; ++j)
cin >> foods[j];
root->Insert(foods, 0); // 트라이 트리 만들고
}
root->Output(0); // DFS 탐색
}
문자열들을 트라이 트리에 모두 저장한 후 DFS 로 탐색하며 출력하면 되는 문제였다. 단, 좀 특이하게 문자 하나 하나씩을 트리에 저장했던 방식이 아닌, 그냥 문자열 자체를 통째로 노드 하나 하나에 저장하는 방식이였다.
3️⃣ 휴대폰 자판 (백준 5670)
문제와 더 자세한 설명은 링크 참고 [백준 5670][💚4] 휴대폰 자판 (트라이, 원하는만큼 입력 받기)
코드 펼쳐서 보기 (Click)
#include <bits/stdc++.h>
using namespace std;
class Trie {
private:
bool isEnd; // 단어의 끝인지 여부
unordered_map<char, Trie*> child; // 자식 링크들을 담은 해시 맵 Key : 자식 문자(다음 글자) Value : 자식 객체 주소
public:
/* 트라이 만들기 */
void Insert(string str) {
Trie* now = this;
for (int i = 0; i < str.length(); ++i) {
if (now->child[str[i]] == nullptr)
now->child[str[i]] = new Trie();
now = now->child[str[i]];
if (i == str.length() - 1)
now->isEnd = true;
}
}
/* 버튼 직접 수동으로 눌러야 하는 개수 */
int AutoComplete(string str) {
int count = 1; // 모든 첫 문자들은 무조건 입력해야하니.. 1 에서 시작
Trie* now = child[str[0]]; // 루트 말고 첫 문자에서 시작하기
for (int i = 1; i < str.length(); ++i) {
if (now->isEnd || now->child.size() > 1) // 현재 문자가 끝이거나 혹은 현재 문자의 자식 문자 개수가 2 이상이라면 수동으로 입력해야 한다. count += 1
count++;
now = now->child[str[i]]; // 다음 자식으로 타고 내려가기
}
return count;
}
public:
};
int main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
while (cin >> n) { // 원하는 만큼 입력 받기!!
vector<string> words(n);
for (int i = 0; i < n; ++i)
cin >> words[i];
// 트라이 만들기
Trie* root = new Trie();
for (int i = 0; i < n; ++i)
root->Insert(words[i]);
// 모든 입력 횟수 합
int sum = 0;
for (int i = 0; i < n; ++i)
sum += root->AutoComplete(words[i]);
double result = (double)sum / words.size();
cout << fixed << setprecision(2) << result << '\n'; // 출력 정밀도 2 자리로 설정
}
}
현재 노드의 자식 노드가 오직 한 개라는 것은 다음 글자로 올 수 있는 글자가 유일하다는 것이므로 자동 입력 될 수 있다. 이렇게 트라이 트리에서 현재 노드의 자식 노드의 개수를 따져 풀이하는 문제였다.
4️⃣ 가사 검색 (카카오 블라인드 공채 2020)
문제와 더 자세한 설명은 링크 참고 [C++로 풀이] 가사 검색 (트라이 자료구조, 문자열 검색, 이분 탐색) ⭐⭐⭐⭐
코드 펼쳐서 보기 (Click)
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Trie {
private:
Trie* child[26]; // 자식 노드 주소 배열 (배열로 바로 접근 가능, 인덱스는 소문자 알파벳 순서에 대응)
int count; // 첫 문자부터 해당 노드의 문자까지를 접두사로 가지는 문자들의 개수 (= )
public:
Trie() : child(), count(0) {} // child 는 null 로, count 는 0 으로 초기화
/* 트라이 만들기 */
void Insert(string str) {
Trie* now = this;
for (char ch : str) {
now->count++; // 방문할 때마다 1 증가해주면 됨
if (now->child[ch - 'a'] == nullptr)
now->child[ch - 'a'] = new Trie(); // 없다면 새로 생성
now = now->child[ch - 'a']; // 트리 타고 내려감
}
}
int Search(string str) {
Trie* now = this;
for (char ch : str) {
if (ch == '?') // ? 면 검사하려는 접두사가 끝났다는 것
return now->count; // 현재 방문중인 노드의 count 를 리턴하고 끝내면 된다.
now = now->child[ch - 'a'];
if (now == nullptr) // 트라이의 끝까지 도달 할 때까지도 해당 접두사와 일치하는 것을 만나지 못했다면 해당 접두사로 시작하는 단어는 없는 것
return 0;
}
return -1; // 코드가 정상적이라면 여기에 걸릴 일은 없다.
}
};
Trie TrieRoot[10000]; // 접두사 찾는 길이별 트리들 (문제에서 최대 길이 10000 이라고 제한함)
Trie ReTrieRoot[10000]; // 접미사 찾는 길이별 트리들! 거꾸로 뒤집은 문자열들을 넣어 접두사 찾듯이 찾을 것
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
/* 트라이 트리 만들기 (개수 구해놓기) */
for (string str : words) {
TrieRoot[str.length() - 1].Insert(str); // 길이에 맞는 트리에 원래 순서대로 추가
reverse(str.begin(), str.end()); // 문자열 뒤집기
ReTrieRoot[str.length() - 1].Insert(str); // 길이에 맞는 트리에 역순서으로 추가
}
/* 트라이 트리 탐색 */
for (string query : queries) {
if (query[0] != '?') // 접두사 : TrieRoot[str.length() - 1] 트리 탐색
answer.push_back(TrieRoot[query.length() - 1].Search(query));
else { // 접미사 : ReTrieRoot[str.length() - 1] 트리 탐색
reverse(query.begin(), query.end()); // 뒤집기. ??and 가 dna?? 가 되도록
answer.push_back(ReTrieRoot[query.length() - 1].Search(query));
}
}
return answer;
}
- 트라이를 순회하면서 지나는 노드마다 1 씩 누적하여 더해주면 루트부터 그 노드까지를 접두사로 하는 단어의 총 개수가 된다.
- 트라이 자료구조 상 중복되는 접두사는 같은 노드를 지나기 때문이다.
- 또한 이 문제에서는 접미사도 요구하는데 접미사는 그냥 거꾸로 reverse 시킨 문자열을 트라이에 넣어 접두사 찾듯이 찾으면 된다.
- 이 문제는 같은 문자열 길이에서의 접두사 개수를 구하는 문제이기 때문에 문자열 길이 별로 따로 따로 트라이 트리를 만든다.
5️⃣ 자동완성 (카카오 블라인드 공채 2018)
문제와 더 자세한 설명은 링크 참고 [C++로 풀이] 자동 완성 (트라이 자료구조) ⭐⭐⭐⭐
코드 펼쳐서 보기 (Click)
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
class Trie {
private:
int count = 0;
unordered_map<char, Trie*> child;
public:
void Insert(string str) {
Trie* now = this;
for (int i = 0; i < str.length(); ++i) {
if (now->child[str[i]] == nullptr)
now->child[str[i]] = new Trie;
now = now->child[str[i]];
now->count++;
}
}
int AutoComplete(string str) {
int numOfInput = 1; // 모든 첫 문자들은 무조건 입력해야하니.. 1 에서 시작
Trie* now = child[str[0]]; // 루트 말고 첫 문자에서 시작하기
for (int i = 1; i < str.length(); ++i) {
if (now->count > 1)
numOfInput++;
now = now->child[str[i]];
}
return numOfInput;
}
};
int solution(vector<string> words) {
int answer = 0;
Trie root;
for (string word : words)
root.Insert(word);
for (string word : words)
answer += root.AutoComplete(word);
return answer;
}
- 이 문제는
isEnd둘 필요가 없을 것 같아 안두었다. (문자열 검색해낼 필요는 없기 때문) - 백준 휴대폰 자판 문제처럼 자동완성 입력 횟수를 구하는 문제인데 백준 문제와는 자동 완성 판별 기준이 좀 다르다.
- 백준 “휴대폰 자판” 👉 다음 글자 후보가 유일해야 다음 글자는 자동완성이 가능
- 자식이 딱 한개인지만 가리면 됐다. 중복 되는게 없거나 접두사가 싹 다 공통적이거나 둘 중 하나여야 가능하기 때문이다.
word,world가 있다면wo까지만 입력 되어도 다음 글자 후보는r뿐이므로r은 자동입력이 됨.
- 카카오 “자동완성” 👉 뒤의 문자열 후보가 유일해야 뒤의 문자열은 자동완성이 가능
- 자식이 한개이되 공통된 접두사이면 안됨. 유일한 문자열이어야 함. 자식이 한개라는 것은 그게 유일해서일 수도 있고 싹 다 공통적인 접두사라 그럴 수도 있어서 이 자식 한 개라는 정보만으로 판별할 수는 없음. 그러므로 노드마다 접두사 횟수 카운팅 미리 해놓아야 한다.
word,world가 있다면wo까지 입력 해도 그 뒤의 문자열이word가 될지,world가 될지 모르기 때문에 자동 입력 되지 않음.
- 백준 “휴대폰 자판” 👉 다음 글자 후보가 유일해야 다음 글자는 자동완성이 가능
🚀 출처 및 참고
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기