Trie

Trie 자료구조 이해하기

[5670 휴대폰 자판] https://www.acmicpc.net/problem/5670 .
트라이 자료구조를 이용한다.

문제상황 파악하기.

휴대폰의 자동완성 기능을 사용했을 때 버튼 누르는 횟수를 계산하는 문제이다.
트라이 자료구조를 이용하여 버튼을 누를 때마다 카운트를 해주면 된다.

Trie가 뭐길래?

트라이 자료구조는 원래 있던 문자면 따라가다가 달라지면 방향을 틀어 새로운 길을 만드는 트리구조이다.
생각하기는 편한 자료구조인데 처음보면은 구현은 어떻게 해야하지 싶다.
기본적으로는 연결리스트의 아이디어이다.
최적화할 때 맵을 이용하는 방법도 있지만 여기서는 알파벳 26개의 배열을 만들어서 트라이를 구현해보자!

아이디어 얻기.

트라이 구조를 만들고 단어가 끝날 때마다 bool형 isEnd에다가 체크를 했다.
그리고 그 단어들을 따라가며 isEnd가 나올 때마다 카운트를 해준다.
그러면 카운트된 수가 문자들을 치기 위해서 타이핑해야하는 숫자이고 이를 문자의 수로 나눠주면 평균이 된다.
이는 문자를 따라가며 단 한번만 수행 되므로 문자의 길이 즉, O(N)의 시간복잡도를 가질 것이다.
다만 알파벳이 새로 생길 때마다 공간을 할당하다보니 메모리의 소모가 크다.

주의할 점

동적할당을 했으면 delete를 이용하여 메모리를 비워야한다.

실제 코드

나머지 주의 할 점은 코드에 주석으로 처리했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define fast_io cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;


const int ALPHABET = 26;

struct Trie{
    Trie *children[ALPHABET];
    bool isEnd;
    Trie(){
        isEnd = false;
        for(int i=0;i<ALPHABET;i++) children[i] = NULL;
    }
    ~Trie(){
        for(int i=0;i<ALPHABET;i++)
            if(children[i]) delete children[i];
    }
};

void insert(Trie* root, string& key, bool isFirst, int idx){
    Trie *pCrawl = root;

    if(!pCrawl->children[key[idx]-'a']) {
        pCrawl->children[key[idx]-'a'] = new Trie();
        if(!isFirst){
            pCrawl -> isEnd = true; //처음으로 갈라지거나 끝나는 부분을 체크했음
            isFirst = true;
        }
    }
    if(idx==key.length()) {
        pCrawl -> isEnd = true;
        return;
    }
    insert(pCrawl->children[key[idx]-'a'], key, isFirst, idx+1);

}

int search(Trie* root, string& key){
    Trie * pCrawl = root;
    int ret = 0;
    for(int i=0;i<key.length();i++){
        int idx = key[i]-'a';
        if(pCrawl->isEnd) ret++;
        pCrawl = pCrawl->children[idx];
    }
    return ret;
}

vector<string> strs;

int main(){
    fast_io;
    int num;
    while (cin>>num){
        strs = vector<string> (num);
        Trie* root = new Trie();
        for(int i=0;i<num;i++){
            cin >> strs[i];
            insert(root, strs[i], false, 0);
        }
        int res = 0;
        for(int i=0;i<num;i++){
            res += search(root, strs[i]);
        }
        cout << fixed;
        cout.precision(2);
        cout << (double)res/(double)num << '\n';
        delete root;
    }
    
}