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

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

두가지 방법이 있었는데 해쉬 그리고 Trie 해쉬를 사용하는 방법으로 했다가 

1. direct addressing 방법은 성공

2. 체이닝 방식 으로 in-direct addressing 방식-> 시간 초과 

Trie 방식으로 하다가 결국..역기에서 짧은 단어의 경우엔 알파벳 역순으로 .. 오답이 나와서 

다시 한번 Mergesort 로 한번더 정열이 필요했다. 

#include <stdio.h>
#include <iostream>
#include <memory.h>
 
 
#define MAX_N 100007
#define MAX_NUM 10021
#define ALPHABET_NUM 57 + 1
 
 
using namespace std;
int AnsNum = 0;
 
 
typedef struct node {
 
    bool finish;
    bool visit;
    bool status;;
 
    node *next[ALPHABET_NUM];
}Node;
 
Node Trie[MAX_N * 5 + 2];
int Allcnt = 0;
 
 
struct Word {
 
    char word[6];
 
    Word &operator =(const Word  &org) {
 
        int i = 0;
        for (i = 0; org.word[i]; i++) {
            word[i] = org.word[i];
        }
 
        word[i] = 0;
 
        return *this;
    }
 
    bool operator <(const Word &other) const {
 
 
        int i = 0;
        for (i = 0; word[i]; i++) {
 
            if (word[i] != other.word[i])
                return word[i] < other.word[i];
        }
        return word[i] < other.word[i];
    }
 
};
 
Word WordAns[MAX_N];
Word  temp[MAX_N];
 
void MergeSort(Word  arr[], int l, int r)
{
 
    if (l == r)
        return;
 
    int half = (l + r) / 2;
    int li = l, ri = half + 1;
    int idx = l;
 
    MergeSort(arr, l, half);
    MergeSort(arr, half + 1, r);
 
 
    while (li <= half && ri <= r) {
 
        if (arr[li] < arr[ri])  temp[idx++] = arr[ri++];
        else temp[idx++] = arr[li++];
 
    }
 
    while (ri <= r) temp[idx++] = arr[ri++];
    while (li <= half) temp[idx++] = arr[li++];
 
 
    for (int i = l; i <= r; i++) {
        arr[i] = temp[i];
    }
 
}
 
 
 
void mystrcpy(char* dest, char* src) {
    while (*src)    *dest++ = *src++;
    *dest = 0;
}
 
// @ 0: same ,other -> not prefectly same 
int Strcmp(const char *src, const char *dst) {
 
    while (*src != '\0' && *src == *dst) {
 
        *src++;
        *dst++;
    }
 
    return *src - *dst;
}
 
void Strcmp(char *dst, const char *src) {
 
    while (*src != '\0') {
        *dst++ = *src++;
    }
 
    *dst++ = '\0';
}
 
 
 
 
int tCnt = 0;
 
 
Node *myAlloc() {
 
    Trie[tCnt].finish = false;
    Trie[tCnt].status = false;
    Trie[tCnt].visit  = false;
 
    for (int i = 0; i < ALPHABET_NUM; i++)
        Trie[tCnt].next[i] = NULL;
 
    return &Trie[tCnt++];
}
 
 
void add(Node *root, char *str, bool status) {
    
    Node *ptr = root;
 
    for (int i = 0; str[i]; i++) {
 
        int idx = str[i] - 'A';
 
        if (!ptr->next[idx]) {
 
            Node *newNode = myAlloc();
            ptr->next[idx] = newNode;
        }
 
        ptr = ptr->next[idx];
    }
 
    ptr->finish = true;
    ptr->status = status;
 
 
}
 
void findTrie(Node *ptr, int idx, char *str) {
 
 
    if (ptr->finish && ptr->status) {
        strcpy(WordAns[AnsNum++].word, str);
        //cout << str << endl;
        //return;
    }
 
    for (int i = ALPHABET_NUM - 1; i >= 0; i--) {
 
        if (ptr->next[i] && !ptr->next[i]->visit) {
 
            str[idx] = i + 'A';
            str[idx + 1] = '\0';
 
            ptr->next[i]->visit = true;
 
            //next 의 point 값을 재귀 함수의 인자로 //
            findTrie(ptr->next[i], idx + 1, str);
 
        }
    }
}
 
int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    freopen("input.txt", "r", stdin);     setbuf(stdout, NULL);
    tCnt = 0;
 
    char status[6];
    char arr[6];
 
    int N;
    scanf("%d", &N);
 
    Node  *root = myAlloc();
 
    for (int i = 0; i < N; i++) {
 
        scanf("%s %s", &arr, &status);
        
        if (status[0] == 'e') {
 
            add(root, arr, true);
    
        }
        else {
 
            add(root, arr, false);            
        }
    }
 
    char str[6];
    str[5] = '\0';
 
    findTrie(root, 0, str);
 
    MergeSort(WordAns, 0, AnsNum - 1);
    for (int i = 0; i < AnsNum; i++)
        cout << WordAns[i].word << "\n";
    
    return 0;
}