07-02 03:43
Notice
Recent Posts
Recent Comments
Link
«   2025/07   »
일 월 화 수 목 금 토
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
Tags more
Archives
Today
Total
관리 메뉴

너와나의 관심사

백준 [회사에 있는 사람]7785 본문

카테고리 없음

백준 [회사에 있는 사람]7785

벤치마킹 2019. 6. 25. 14:57

회사에 있는 사람 




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



해당 코드는 메모리.. 초과로 성공하지는 못했지만 Trie 자료구조를 활용해서 ..  재귀적인 방법으로 Name 을 printout 하는데 

기록을 남기기 위해서 포스팅 

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
#include <stdio.h>
#include <iostream>
#include <memory.h>
 
#define MAX_N 1000001
using namespace std;
//#define ALPHABET_NUM 26
#define ALPHABET_NUM 57 +1
 
struct Node {
 
    bool finish;
    bool staus;
    Node *next[ALPHABET_NUM];
 
}Trie[MAX_N];
 
 
int NodeCnt = 0;
 
Node *myAlloc() {
 
    for (int i = 0; i < ALPHABET_NUM; i++)
    {
        Trie[NodeCnt].next[i] = NULL;
    }
 
    Trie[NodeCnt].staus = false;
    Trie[NodeCnt].finish = false;
 
    return &Trie[NodeCnt++];
}
 
void add(Node *root, char *str, bool status)
{
 
    Node * ptr = root;
 
    for (int i = 0; str[i]; i++) {
 
        int nIdx = str[i] - 'A';
 
        if (ptr->next[nIdx]) {
            ptr = ptr->next[nIdx];
        }
        else {
 
            Node *nNode = myAlloc();
 
            ptr->next[nIdx] = nNode;
            ptr = ptr->next[nIdx];
        }
    }
 
    ptr->finish = true;
    ptr->staus = status;
}
 
char Name[6];
 
void PrintName(Node *ptr, char *str, int idx) {
 
    if (ptr->finish && ptr->staus)
        cout << str << "\n";
 
    for (int i = ALPHABET_NUM - 1; i >= 0; i--) {
 
        if (ptr->next[i])
        {
            str[idx] = i + 'A';
            str[idx + 1] = 0;
 
            PrintName(ptr->next[i], str, idx + 1);
        }
    }
}
 
int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    freopen("input.txt", "r", stdin); setbuf(stdout, NULL);
 
    char status[6];
    char arr[6];
    int N;
    cin >> N;
 
    Node *root = myAlloc();
 
    for (int i = 0; i < N; i++) {
 
        cin >> arr >> status;
 
 
        if (status[0] == 'e') {
            add(root, arr, true);
        }
        else {
            add(root, arr, false);
        }
    }
 
    char Name[6];
    PrintName(root, Name, 0);
 
    //    cout << "Test " << endl;
 
    return 0;
}
cs


저작자표시 (새창열림)
Comments