-
Trie학교 수업/자료구조 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);
}