01-25 16:17
Recent Posts
Recent Comments
관리 메뉴

너와나의 관심사

Tire 자료구조에서 메모리 줄여서 구현 본문

카테고리 없음

Tire 자료구조에서 메모리 줄여서 구현

벤치마킹 2019. 7. 1. 00:29

Trie 메모리 때문에 Node * ptr 대신에 integer 형태로 코드 변환 



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;
}
    



Comments