백준 05670 - 휴대폰 자판

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

5670번: 휴대폰 자판

 

고려사항

- 트라이 자료구조 사용

- 매 테스트 케이스마다 다른 사전 구성이니 꼭 delete root 로 메모리 관리하기.

- 단어의 첫 글자를 추론하지 않는다 => 2번째 테스트 케이스처럼 모든 단어가 한 알파벳으로 시작하면

코드의 로직은 총 버튼 클릭수를 정답보다 n 번만큼 뺀 만큼 구한다. root의 nextCnt 가 1이라 +1을 안해주기 때문!

따라서 root->nextCnt == 1 이라면 sum += n 실행!

- hell, hello 의 경우를 잘 분석한다 => 다음 알파벳이 하나 뿐이고, 현재 알파벳에서 term 이라면 ++nextCnt

- scanf는 입력 받은 인자? 수 를 return 한다 => eof 시 -1

 

#include <cstdio>
using namespace std;

struct trie{
    bool term;
    int nextCnt;
    trie *next[26];

    trie(){
        term = false;
        nextCnt = 0;
        for(int i=0;i<26;++i){
            next[i] = NULL;
        }
    }

    ~trie(){
        for(int i=0;i<26;++i){
            delete next[i];
        }
    }

    void insert(char *str){
        if(*str == '\0'){
            ++nextCnt;
            term = true;
        }else{
            int tmp = *str - 'a';

            if(!next[tmp]){
                next[tmp] = new trie();
                ++nextCnt;
            }
            next[tmp]->insert(str+1);
        }
    }

    int find(char *str, int cnt){
        if(*str == '\0'){
            if(term){
                return cnt;
            }else{
                return -1;
            }
        }else{
            int tmp = *str - 'a';
            if(!next[tmp]){
                return -1;
            }else{
                if(nextCnt == 1){
                    return next[tmp]->find(str+1, cnt);
                }
                return next[tmp]->find(str+1, cnt+1);
            }
        }
    }
};

int main() {

    int n;
    float sum, ans;
    char str[100000][81];

    while(scanf("%d", &n) > 0){
        trie *root = new trie();

        sum = 0;
        for(int i=0;i<n;++i){
            scanf("%s", str[i]);
            root->insert(str[i]);
        }

        for(int i=0;i<n;++i){
            sum += root->find(str[i], 0);
        }

        if(root->nextCnt == 1){
            sum += n;
        }
        ans = sum / n;
        printf("%.2f\n", ans);

        delete root;
    }

    return 0;
}