[알고리즘] 백준 1764번 - 듣보잡

#라이브러리 없이 코딩하기

 

 

구현 알고리즘

• Hash

• Merge Sort

 

소스 코드

#include <stdio.h>
#define MAX_TABLE 500017
struct Hash {
    char name[21];
    Hash* next;
} h[MAX_TABLE], * ht[MAX_TABLE], * target[MAX_TABLE];
int h_idx = 0, t_idx = 0;

unsigned long getHash(const char* str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c);
    }

    return hash;
}

int mstrcmp(const char* a, const char* b) {
    while (*a && *a == *b) {
        ++a; ++b;
    }
    return *a - *b;
}
void mstrcpy(char* dst, const char* src) {
    while (*src)
        *dst++ = *src++;
    *dst = '\0';
}

void mergeSort(int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(start, mid);
        mergeSort(mid + 1, end);

        int s1 = start;
        int s2 = mid + 1;
        int idx = start;
        while (s1 <= mid && s2 <= end) {
            if (mstrcmp(target[s1]->name, target[s2]->name) <= 0) {
                ht[idx++] = target[s1++];
            }
            else {
                ht[idx++] = target[s2++];
            }
        }
        while (s1 <= mid) ht[idx++] = target[s1++];
        while (s2 <= end) ht[idx++] = target[s2++];

        for (int i = start; i <= end; i++)
            target[i] = ht[i];
    }
}

int main() {
    int n, m;

    scanf("%d %d", &n, &m);

    char name[21];
    for (int i = 0; i < n; i++) {
        scanf("%s", name);

        unsigned long key = getHash(name) % MAX_TABLE;

        Hash* newH = &h[h_idx++];
        mstrcpy(newH->name, name);

        newH->next = ht[key];
        ht[key] = newH;
    }

    for (int i = 0; i < m; i++) {
        scanf("%s", name);

        unsigned long key = getHash(name) % MAX_TABLE;
        for (Hash* cur = ht[key]; cur != 0; cur = cur->next) {
            if (mstrcmp(cur->name, name) == 0) {
                target[t_idx++] = cur;
                break;
            }
        }
    }

    mergeSort(0, t_idx - 1);

    printf("%d\n", t_idx);
    for (int i = 0; i < t_idx; i++) {
        printf("%s\n", target[i]->name);
    }
}