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

은 바로 다음 주 미래의 나

 

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

 

 

구현 알고리즘

• Hash

• Merge Sort

 

생각해 볼 거리

• Quick Sort로 구현해보기

 

소스 코드

#include <stdio.h>

#define MAX_TABLE 1000017

struct Hash {
    char name[6];
    bool in;
    Hash* next;
} h[MAX_TABLE], * ht[MAX_TABLE], * workin[MAX_TABLE];
unsigned int h_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(workin[s1]->name, workin[s2]->name) >= 0) {
                ht[idx++] = workin[s1++];
            }
            else {
                ht[idx++] = workin[s2++];
            }
        }
        while (s1 <= mid) ht[idx++] = workin[s1++];
        while (s2 <= end) ht[idx++] = workin[s2++];

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

int main() {
    int n; // >=2, <=1,000,000

    scanf("%d", &n);

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

        unsigned long key = getHash(name) % MAX_TABLE;

        if (state[0] == 'e') {
            bool exists = false;
            for (Hash* cur = ht[key]; cur != 0; cur = cur->next) {
                if (mstrcmp(cur->name, name) == 0) {
                    exists = cur->in = true;
                }
            }

            if (!exists) {
                Hash* newH = &h[h_idx++];
                newH->in = true;
                mstrcpy(newH->name, name);

                newH->next = ht[key];
                ht[key] = newH;
            }
        }
        else {
            for (Hash* cur = ht[key]; cur != 0; cur = cur->next) {
                if (mstrcmp(cur->name, name) == 0) {
                    cur->in = false;
                }
            }
        }
    }

    // sort
    int w_idx = 0;
    for (int i = 0; i < h_idx; i++) {
        if (h[i].in)
            workin[w_idx++] = &h[i];
    }
    mergeSort(0, w_idx - 1);

    // result
    for (int i = 0; i < w_idx; i++) {
        printf("%s\n", workin[i]->name);
    }
    
    return 0;
}

 

 

! quickSort 사용해서 나중에 다시 구현해보기. 시간 초과가 난다. 다시 공부해보도록 하자.

void swap(Hash *arr[MAX_TABLE], int a, int b) {
    Hash* tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

int partition(Hash *arr[MAX_TABLE], int left, int right) {
    int low = left + 1;
    int high = right;

    while (low <= high) {
        while (low <= right && mstrcmp(arr[left]->name, arr[low]->name) <= 0) {
            //피벗보다 큰 값 찾기
            low++;
        }
        while (high >= left + 1 && mstrcmp(arr[left]->name, arr[high]->name) > 0) {
            high--;
        }
        if (low <= high)
            swap(arr, low, high);
    }
    swap(arr, left, high);
    return high;
}

void quickSort(Hash *unsorted[MAX_TABLE], int left, int right) {
    if (left < right) {
        int pivot = partition(unsorted, left, right);
        quickSort(unsorted, left, pivot-1);
        quickSort(unsorted, pivot + 1, right);
    }
}