카테고리 없음

백준 5670 휴대폰 자판

벤치마킹 2019. 6. 28. 16:09

int 배열로 Linked list 구현해보기 



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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <stdio.h>
#include <iomanip>
 
 
using namespace std;
 
#define MAX_N 100005
#define ALPHABET_NUM 26
 
 
int nodeCnt = 0;
 
struct Node {
 
    bool finish;
    int child[ALPHABET_NUM];
    int NumNextWord;
 
} trieNode[1000001];
 
 
char arr[MAX_N][81];
 
int myAlloc() {
 
    nodeCnt;
 
    for (int i = 0; i < ALPHABET_NUM; i++) {
        trieNode[nodeCnt].child[i] = -1;
    }
 
    trieNode[nodeCnt].finish = false;
    trieNode[nodeCnt].NumNextWord = 0;
 
    return nodeCnt++;
}
 
 
 
void add(int root, char *str) {
 
    int cur = root;
    int i;
 
    for (i = 0; str[i]; i++) {
 
        int Idx = str[i] - 'a';
 
        if (trieNode[cur].child[Idx] != -1) {
 
            cur = trieNode[cur].child[Idx];
 
        }
        else {
 
            int nxt = myAlloc();
            
 
            //next 의 값이 있기 때문에//
            trieNode[cur].child[Idx] = nxt;
            trieNode[cur].NumNextWord++;
 
            cur = nxt;
 
        }
    }
    trieNode[cur].finish = true;
}
 
 
int find(int root, char* str) {
 
    int cur = root;
    int ret = 0;
 
    for (int i = 0; str[i]; i++) {
 
        int Idx = str[i] - 'a';
 
        //0은 무조건 //
        if (i == 0)
            ret++;
        else if (trieNode[cur].NumNextWord > 1)
            ret++;
        else if (trieNode[cur].finish)
            ret++;
 
        cur = trieNode[cur].child[Idx];
    }
 
    return ret;
}
 
 
int N, M;
 
 
int main() {
 
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
 
    freopen("input.txt", "r", stdin); setbuf(stdout, NULL);
    int inpNum = 0;
 
    while (cin >> N) {
 
        //count 초기화 //
        nodeCnt = 0;    
        int root = myAlloc();
 
 
        for (int i = 1; i <= N; i++) {
 
            cin >> arr[i];
            add(root, arr[i]);
        }
 
 
        int typeNum = 0;
 
        for (int i = 1; i <= N; i++) {
 
            typeNum += find(root, arr[i]);
        }
 
        printf("%.2lf\n", (double)typeNum / N);
 
        //cout << fixed << setprecision(2) << (double)typeNum / (double)N << '\n';
    }
 
    return 0;
}
    
cs


저작자표시 (새창열림)