[알고리즘] 백준 7785번: 회사에 있는 사람 -C/C++

백준 7785번: 회사에 있는 사람   https://www.acmicpc.net/problem/7785

 

<활용 알고리즘>

1. HASH(Single Linked List)

2. Merge Sort

(라이브러리 사용하지 않고 직접 구현)

 

<코드>

<stdio.h>
#define NODE_MAX 1000001
#define HASH_MAX 10007

struct NODE {
    bool isEnter;
    char name[6];
    NODE* prev;
} node[NODE_MAX];
int index = 0;
NODE* hashTable[HASH_MAX];

NODE* allNode[NODE_MAX];
NODE* enterNode[NODE_MAX];
NODE* bufferNode[NODE_MAX];
int cntAll = 0;
int cntEnter = 0;

char* enter = "enter";
char* leave = "leave";

void mystrcpy(char* dest, char* src) {
    while(*src)    *dest++ = *src++;
    *dest = 0;
}

int mystrcmp(const char* a, const char* b) {
    while(*a && *a == *b) {
        ++a; ++b;
    }
    return *a - *b;
}

unsigned long myhash(const char *str) {
    unsigned long hash = 5381;
    int c;
    while (c = *str++)  hash = (((hash << 5) + hash) + c) % HASH_MAX;
    return hash % HASH_MAX;
}

void mergeSort(int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(start, mid);
        mergeSort(mid + 1, end);
        
        int i = start;
        int j = mid + 1;
        int k = start;
        while (i <= mid && j <= end) {
            if(mystrcmp(enterNode[i]->name, enterNode[j]->name) >= 0) {
                bufferNode[k++] = enterNode[i++];
            } else {
                bufferNode[k++] = enterNode[j++];
            }
        }
        while(i <= mid) bufferNode[k++] = enterNode[i++];
        while(j <= end) bufferNode[k++] = enterNode[j++];
        
        for(int l = start; l <= end; ++l) {
            enterNode[l] = bufferNode[l];
        }
    }
}

NODE* myalloc() {
    return &node[index++];
}

void init() {
    index = 0;
    for(int i = 0; i < HASH_MAX; ++i){
        hashTable[i] = NULL;
    }
}

int main(int argc, const char * argv[]) {
    init();
    int N;
    scanf("%d", &N);
    for(int n = 0; n < N; ++n) {
        char name[6], isEnter[6];
        scanf("%s %s", name, isEnter);
        
        unsigned long key = myhash(name);
        
        if(mystrcmp(isEnter, enter) == 0) {
            bool hasNode = false;
            for(NODE* pp = hashTable[key]; pp; pp = pp->prev) {
                if(mystrcmp(pp->name, name) == 0) {
                    hasNode = true;
                    pp->isEnter = true;
                    break;
                }
            }
            if(!hasNode) {
                NODE* newNode = myalloc();
                mystrcpy(newNode->name, name);
                newNode->isEnter = true;
                newNode->prev = hashTable[key];
                hashTable[key] = newNode;
                
                allNode[cntAll++] = newNode;
            }
        }
        else if(mystrcmp(isEnter, leave) == 0) {
            for(NODE* pp = hashTable[key]; pp; pp = pp->prev) {
                if(mystrcmp(pp->name, name) == 0) {
                    pp->isEnter = false;
                    break;
                }
            }
        }
    }
    for(int i = 0; i < cntAll; ++i) {
        if(allNode[i]->isEnter) enterNode[cntEnter++] = allNode[i];
    }
    mergeSort(0, cntEnter - 1);
    for(int i = 0; i < cntEnter; ++i) {
        printf("%s\n", enterNode[i]->name);
    }
    
    return 0;
}