5670 휴대폰 자판

TRIE 문제.

TRIE를 만들면서 지나간 node에 cnt++을 한다.

현재 cnt와 자식의 cnt가 같으면 경로가 유일한 것이므로 자동완성 된다.

반대로 다르면 경로가 갈라지는 것이므로 자식의 cnt만큼 더해주면 된다.

자식의 cnt만큼 더해주는 이유는 해당 경로로 흘러간 단어들을 타이핑하려면 무조건 해당 갈라지는 경로에 해당하는 문자를

매 문자열마다 타이핑 해야 하기 때문이다.

#include <stdio.h>
 
struct TRIE {
    TRIE* c[26];
    int pc;
    TRIE() {
        for (int i = 0; i < 26; i++) c[i] = nullptr;
        pc = 0;
    }
    ~TRIE() {
        for (int i = 0; i < 26; i++) 
            delete c[i];
    }
    void insert(char* key) {
        if (*key == 0) {
            pc++;
            return;
        }
        else {
            int next = key[0] - 'a';
            if (!c[next]) {
                c[next] = new TRIE;
            }
            pc++;
            c[next]->insert(key + 1);
        }
    }
};
 
int dfs(TRIE* cur) {
    int ans = 0;
    for (int i = 0; i < 26; i++) {
        if (cur->c[i] == nullptr) continue;
        if (cur->c[i]->pc != cur->pc) {
            ans += cur->c[i]->pc;
        }
        if (cur->c[i]->pc == 1) continue;
        ans += dfs(cur->c[i]);
    }
    return ans;
}
 
int t, n;
 
int main() {
    //freopen("Text.txt", "r", stdin);
    while (scanf("%d", &n) != EOF) {
        TRIE* r = new TRIE;
        char s[82];
        for (int i = 0; i < n; i++) {
            scanf("%s", &s);
            // TRIE
            r->insert(s);
        }
        r->pc++;
        int res = dfs(r);
        printf("%.2lf\n", double(res) / double(n));
        delete r;
    }
    return 0;
}