행복의 주문, 디리릿!!

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

구현 알고리즘

• Merge Sort

• Quick Sort

다음번에 시도해 보기

• 퀵소트로 구현하면 시간을 더 단축시킬 수 있는 문제인 것 같으니 도전해보기 (머지소트 실행시간 : 80ms)

+ 퀵소트는 시간을 단축시키지는 않았지만, 머지소트에 사용되는 포인터 어레이 만큼의 메모리 사용량을 줄일 수 있었다.

(아래 : merge sort, 위 : quick sort)

소스 코드 (merge sort)

#include <stdio.h>

#define MAX_NODE 100001

struct Node {
	char name[11];
	int korean, english, math;
} nodes[MAX_NODE], *nt[MAX_NODE], *tmp[MAX_NODE];

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

int cmpScore(Node *n1, Node *n2) {

	if (n1->korean != n2->korean)
		return n1->korean - n2->korean;
	if (n1->english != n2->english)
		return n2->english - n1->english;
	if (n1->math != n2->math)
		return n1->math - n2->math;
	return mstrcmp(n1->name, n2->name);
}

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 (cmpScore(nt[s1], nt[s2]) > 0)
				tmp[idx++] = nt[s1++];
			else
				tmp[idx++] = nt[s2++];
		}
		while (s1 <= mid) tmp[idx++] = nt[s1++];
		while (s2 <= end) tmp[idx++] = nt[s2++];

		for (int i = start; i <= end; i++)
			nt[i] = tmp[i];
	}
}

int main() {
	int n;
	scanf("%d", &n);

	char name[11];
	int a, b, c;
	for (int i = 0; i < n; i++) {
		scanf("%s %d %d %d", name, &a, &b, &c);

		Node* newN = &nodes[i];
		mstrcpy(newN->name, name);
		newN->korean = a;
		newN->english = b;
		newN->math = c;

		nt[i] = newN;
	}

	mergeSort(0, n-1);

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

소스코드 (quick sort)

#include <stdio.h>

#define MAX_NODE 100001

struct Node {
	char name[11];
	int korean, english, math;
} nodes[MAX_NODE], * nt[MAX_NODE];

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

int cmpScore(Node *n1, Node *n2) {

	if (n1->korean != n2->korean)
		return n1->korean - n2->korean;
	if (n1->english != n2->english)
		return n2->english - n1->english;
	if (n1->math != n2->math)
		return n1->math - n2->math;
	return mstrcmp(n1->name, n2->name);
}

void quickSort(int start, int end) {
	if (start >= end) return;

	int pivot = start;
	int i = pivot + 1;
	int j = end;
	Node* tmp;

	while (i <= j) {
		while (i <= end && cmpScore(nt[i], nt[pivot]) > 0)
			i++;
		while (j > start && cmpScore(nt[j], nt[pivot]) < 0)
			j--;
		
		if (i > j) {
			tmp = nt[j];
			nt[j] = nt[pivot];
			nt[pivot] = tmp;
		}
		else {
			tmp = nt[i];
			nt[i] = nt[j];
			nt[j] = tmp;
		}

	}

	quickSort(start, j - 1);
	quickSort(j + 1, end);
}

int main() {
	int n;
	scanf("%d", &n);

	char name[11];
	int a, b, c;
	for (int i = 0; i < n; i++) {
		scanf("%s %d %d %d", name, &a, &b, &c);

		Node* newN = &nodes[i];
		mstrcpy(newN->name, name);
		newN->korean = a;
		newN->english = b;
		newN->math = c;

		nt[i] = newN;
	}

	//mergeSort(0, n-1);
	quickSort(0, n - 1);

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

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

구현 알고리즘

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

은 바로 다음 주 미래의 나

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

구현 알고리즘

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

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

#이지만 atoi는 직접 구현하니 시간초과라

#라이브러리 사용

구현 알고리즘

• Hash

생각해 볼 거리

• 이중 for loop 안에서 break를 사용하면 왜 실행 시간이  8ms 늘어날까?

• 시간 초과 나지 않도록 atoi 직접 구현해보기

소스 코드

#include <stdio.h>
#include <stdlib.h>

#define MAX_TABLE 100017
#define MAX_NAME 21

struct Hash {
    char name[MAX_NAME];
    Hash* next;
    unsigned long int idx;
} h[MAX_TABLE], * ht[MAX_TABLE];
unsigned int h_idx = 1;

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

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

    return hash;
}

void mstrcpy(char* dst, const char* src) {
    while (*src)
        *dst++ = *src++;
    *dst = '\0';
}

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

int main() {

    int m, n; // >=1 , <= 100,000
    scanf("%d %d", &m, &n);

    char name[MAX_NAME];
    for (int i = 1; i <= m; i++) {
        scanf("%s", name);

        unsigned long key = getHash(name) % MAX_TABLE;

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

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

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

        if ('0' <= name[0] && name[0] <= '9') {
            printf("%s\n", h[atoi(name)].name);
        }
        else {
            unsigned long key = getHash(name) % MAX_TABLE;

            for (Hash* cur = ht[key]; cur != 0; cur = cur->next) {
                if (!mstrcmp(cur->name, name)) {
                    printf("%d\n", cur->idx);
                }
            }
        }
    }
}