[5670번] 휴대폰 자판

문제 출처 :

https://www.acmicpc.net/problem/5670

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트라이

이 문제는 블로그에서 검색하면 하나 더 나오는데

지금것은 for문으로 트라이를 구성했고 검색해서 나오는 내용은 재귀로 트라이를 구성한 것의 차이뿐이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
 
using namespace std;
 
const int MAX_NODE = 26;
 
struct Trie {
    Trie *next[MAX_NODE];
    bool isEnd;
    int child;
    Trie() {
        for (int i = 0; i < MAX_NODE; i++){
            next[i] = nullptr;
            isEnd = false;
            child = 0;
        }
    }
    ~Trie() {
        for (int i = 0; i < MAX_NODE; i++) {
            if (next[i])
                delete next[i];
        }
    }
    
    void del() {
        for (int i = 0; i < MAX_NODE; i++) {
            if (next[i])
                delete next[i];
        }
    }
};
 
int search(char *str, Trie *root) {
    Trie *pos = root;
 
    int ret = 0;
    for (int i = 0; i < str[i]; i++)
    {
        int nowCh = str[i] - 'a';
        if (i && (pos->child >= 2 || (pos->child == 1 && pos->isEnd)))
            ret++;
 
        pos = pos->next[nowCh];
    }
 
    return ret;
}
 
char str[100002][100];
 
int main() {
 
    int n;
    while (scanf("%d", &n) != EOF) {
        Trie *root = new Trie;
 
        for (int i = 0; i < n; i++)
        {
            scanf("%s", str[i]);
            
            Trie *pos = root;
            for (int j = 0; j < str[i][j]; j++) {
                int nowCh = str[i][j] - 'a';
 
                if (pos->next[nowCh] == nullptr)
                {
                    pos->next[nowCh] = new Trie;
                    pos->child++;
                }
                pos = pos->next[nowCh];
            }
            pos->isEnd = true;
        }
 
        int ans = n;
        for (int i = 0; i < n; i++)
            ans += search(str[i], root);
        
        printf("%.2lf\n", 1.0 * ans / n);
 
        root->del();
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>