[알고리즘] 백준 1764번: 듣보잡 -C/C++

 

백준 1764번: 듣보잡   https://www.acmicpc.net/problem/1764

 

<활용 알고리즘>

1. HASH(Single Linked List)

2. Merge Sort

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

 

<코드>

#include <stdio.h>
#define HASH_MAX 10007
#define NODE_MAX 500001
#define NAME_MAX 500001

struct NODE {
    char name[21];
    NODE* prev;
} node[NODE_MAX];
int index = 0;

NODE* hashTable[HASH_MAX];
char* DBJ[NAME_MAX];
char* tempDBJ[NAME_MAX];

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

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

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(DBJ[i], DBJ[j]) <= 0)
                tempDBJ[k++] = DBJ[i++];
            else
                tempDBJ[k++] = DBJ[j++];
        }
        while(i <= mid) tempDBJ[k++] = DBJ[i++];
        while(j <= end) tempDBJ[k++] = DBJ[j++];
        
        for(int l = start; l <= end; ++l){
            DBJ[l] = tempDBJ[l];
        }
    }
}

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

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[]) {
    int N,M;
    int count = 0;
    init();
    scanf("%d %d\n", &N, &M);
    char name[21];
    for (int i = 0; i < N; ++i){
        scanf("%s", name);
        
        NODE* newNode = myalloc();
        mystrcpy(newNode->name, name);
        
        unsigned long key = myhash(name);
        newNode->prev = hashTable[key];
        hashTable[key] = newNode;
    }
    for (int i = 0; i < M; ++i) {
        scanf("%s", name);
        
        unsigned long key = myhash(name);
        
        for(NODE* pp = hashTable[key]; pp; pp = pp->prev){
            if(!mystrcmp(name, pp->name)) {
                DBJ[count++] = pp->name;
            }
        }
    }
    printf("%d\n", count);
    
    mergeSort(0, count - 1);
    for(int i = 0; i < count; ++i){
        printf("%s\n", DBJ[i]);
    }
    return 0;
}