[5670번] 휴대폰 자판

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트라이

이 문제는 트라이의 기본인 insert와 새로 만든 search로 문제를 풀어보려 한다.

search의 원리는 다음과 같다.

cnt 의미 :: 현재 트라이가 가지는 존재하는 알파벳 수가 2개 이상이라면 (예를들어, hello와 love에서 h와 l이 첫번째에서 2개이다.)

따라서 cnt >= 2이거나, cnt == 1 && finish -> 즉, cnt == 1인데 마지막인경우 혹은 시작인 경우

(시작인 경우는 무조건 1번 누르게 된다.) 이런 경우는 무조건 + 1을 해준다.

이 3가지 조건을 이용하면 문제를 해결 할 수 있다.

소스 코드 : 

1 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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <memory.h>   using namespace std;   const int TrieNode = 26;   struct Trie {     Trie *next[TrieNode];     bool start, finish;     bool nextChild;     int cnt = 0;       Trie() {         fill(next, next + TrieNode, nullptr);         start = finish = nextChild = false;         cnt = 0;     }       ~Trie() {         for(int i = 0; i < TrieNode; i++)             if (next[i])                 delete next[i];     }          bool insert(const char *key, bool isStart){         if (isStart)             start = true;           if (*key == '\0')         {             finish = true;               return true;         }           int nextKey = *key - 'a';           if (!next[nextKey])         {             next[nextKey] = new Trie;             cnt++;         }         nextChild = true;           return next[nextKey]->insert(key + 1, false);       }       int search(const char *key){         int ret = 0;         if (*key == '\0')             return ret;                  int nextKey = *key - 'a';           if (cnt >= 2 || (cnt == 1 && finish) || start)             ret += 1;             ret += next[nextKey]->search(key + 1);         return ret;                } };   char str[100002][82]; int main() {     int n;     while (scanf("%d", &n) != EOF)     {         for (int i = 0; i < n; i++)             scanf("%s", str[i]);           Trie *root = new Trie;           for (int i = 0; i < n; i++)             root->insert(str[i], true);                  int ret = 0;         for (int i = 0; i < n; i++)         {               ret += root->search(str[i]);         //    cout << "str :: " << str[i] << " ret :: " << ret << endl;         }         printf("%.2lf\n", 1.0*ret / n);           delete root;     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus