컴영
2020. 9. 9. 18:23
Trie(트라이)
- 개념 : 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
- 사용 목적 : 문자열 탐색 ex) 검색어 자동완성, 사전에서 찾기, 문자열 검사
- 구현 코드
예시문제 ) [프로그래머스] 자동완성
https://programmers.co.kr/learn/courses/30/lessons/17685
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <string>
#include <vector> #include <iostream>
using namespace std;
#define ALPHA 26
struct Trie {
bool finish; //문자열의 끝인지 확인하는 변수
int cnt;//현재 노드를 기준으로 아래에 몇개의 문자열이 존재하는지
Trie *child[26];
//생성자
Trie() {
finish = false;
for (int i = 0; i < 26; i++) child[i] = NULL;
cnt = 0;
}
~Trie() {
for (int i = 0; i < 26; i++) if (child[i]) delete child[i];
}
void insert(const char *key) {
cnt++;
if (*key == NULL) {
finish = true;
return;
}
int cur = *key - 'a';//0~26사이의 수로 바꿈
if (child[cur] == NULL) child[cur] = new Trie();
child[cur]->insert(key + 1);
}
int find(const char *key, int depth) {
if (cnt == 1 || *key == NULL) return depth;
int cur = *key - 'a';
return child[cur]->find(key + 1, depth + 1);
}
};
int solution(vector<string> words) {
int answer = 0;
Trie * root = new Trie();
for(string str : words){
root->insert(str.c_str());
}
for(string str : words){
answer += root->find(str.c_str(),0);
}
return answer;
}
|
문자열을 존재하는 지 알아보는 코드는
bool exist(cont char * key){
if(*key == NULL && finish) return true;
int cur = *key - 'a';
if(child[cur] == NULL) return false;
return child[cur]->exist(key+1);
}