휴대폰 자판




문자열들을 트라이로 저장해둔다.

탐색시마다 다음 트라이로 넘어갈 때 가능성이 하나 밖에 없으면 자동완성된다.

단 처음글자는 무조건 쳐야한다.



트라이에 딸린 트라이의 갯수를 알고, 빠르게 다음 트라이로 넘어가야 한다.


또한 자동완성여부를 판단하는데 있어서, 지금까지 지나온 트라이들이 다른 문자열을 포함하는지도 확인해야 한다.


hello의 경우 탐색하는데 l부터는 자식 트라이가 하나씩 밖에 없지만,


hell이란 다른 문자열이 먼저 끝나기 때문에 o를 추가로 쳐야 한다.



따라서 트라이 구조체에 문자열이 끝났는지를 판별하는 변수와, 자식 트라이의 수를 알려주는 변수를 추가한다.


탐색중에 버튼을 누르는 경우는 다음의 세가지다.


1. 처음 버튼을 누를 때


2. 자식 수가 2개 이상일 때


3. end를 지나칠 때



HELLO를 탐색할 때의 과정이다.


처음 버튼을 누를 때 +1


HE다음 자식이 두 개니까 +1


HELL이란 작은 문자열이 있었으니까 +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
#include <iomanip>
#include<iostream>
using namespace std;
 
#define alpha 26
#define maxn 100000
bool inital;
int ans, n;
char arr[maxn][81];
 
struct trie {
    trie* pan[alpha];
    bool end;
    int cnt;
 
    trie() {
        for (int i = 0; i < alpha; ++i)
            pan[i] = nullptr;
        end = false;
        cnt = 0;
    }
    ~trie() {
        for (int i = 0; i < alpha; ++i)
            if (pan[i] != nullptr)
                delete pan[i];
    }
 
    void insert(char* str) {
        if (*str == '\0') {
            end = true;
            return;
        }
            
 
        int cur = *str - 'a';
        if (pan[cur] == nullptr) {
            pan[cur] = new trie();
            cnt++;
        }
        pan[cur]->insert(str + 1);
    }
 
    void find(char* str) {
        if (*str == '\0')
            return;
 
        if (inital) {
            inital = false;
            ans++;
        }
        else {
            if (end)
                ans++;
            else if (cnt > 1)
                ans++;
        }
            
        int cur = *str - 'a';
        pan[cur]->find(str + 1);
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin>>n) {
        trie* root = new trie();
        ans = 0;
 
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
            root->insert(arr[i]);
        }
            
        for (int i = 0; i < n; ++i) {
            inital = true;
            root->find(arr[i]);
        }
 
        cout << fixed << setprecision(2)<< (double)ans / (double)n<<'\n';
        delete root;
 
    }
    return 0;
}
cs



'알고리즘 > Trie 트라이' 카테고리의 다른 글

백준) 5052 전화번호 목록  (0) 2018.01.29

전화번호 목록


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




트라이 구조체의 10칸짜리 숫자 판을 보면서, 중간에 끝나는 문자열이 삽입되었는지를 기억해야 한다.


따라서 구조체에 끝났는지 기억하는 변수를 추가해줘서, 삽입함수가 끝날 때 해당 구조체에 기록해둔다.



이제 모든 전화번호들을 트라이들을 헤집으면서 탐색할 때, 아직 전화번호가 끝나지 않았는데, 끝났다는 기록이 나오면


일관성 없는 목록임을 알 수 있다.





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
#include <stdio.h>
#define num 10
#define maxn 10000
 
struct trie {
    trie* pan[num];
    bool end;
 
    trie() {
        for (int i = 0; i < num; ++i)
            pan[i] = nullptr;
        end = false;
    }
    ~trie() {
        for (int i = 0; i < num; ++i)
            if (pan[i] != nullptr)
                delete pan[i];
    }
 
    void insert(char* str) {
        if (*str == '\0') {
            end = true;
            return;
        }
        //종료
        int cur = *str - '0';
        if (pan[cur] == nullptr)
            pan[cur] = new trie();
        pan[cur]->insert(str + 1);
    }
 
    int find(char* str) {
        if (*str == '\0')
            return 0;
 
        if (end)
            return 1;
 
        int cur = *str - '0';
        return pan[cur]->find(str + 1);
    }
};
 
int t, n;
char buf[maxn][11];
 
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d"&n);
 
        trie* root = new trie();
 
        for (int i = 0; i < n; ++i) {
            scanf("%s", buf[i]);
            root->insert(buf[i]);
        }
        
        bool ans = true;
        for (int i = 0; i < n; ++i) {
            if (root->find(buf[i])) {
                ans = false;
                break;
            }
        }
        if (ans)
            puts("YES");
        else
            puts("NO");
 
        delete root;
    }
}
cs


'알고리즘 > Trie 트라이' 카테고리의 다른 글

백준) 5670 휴대폰 자판  (0) 2018.01.29

+ Recent posts