반응형
은 바로 다음 주 미래의 나
#라이브러리 없이 코딩하기
구현 알고리즘
-
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);
}
}반응형
'알고리즘' 카테고리의 다른 글
| [알고리즘] 백준 10825번 - 국영수 (0) | 2021.03.11 |
|---|---|
| [알고리즘] 백준 1764번 - 듣보잡 (0) | 2021.03.11 |
| [알고리즘] 백준 1620번 - 나는야 포켓몬 마스터 이다솜 (0) | 2021.03.11 |
| [LeetCode] 1. Two Sum _Python 딕셔너리 (0) | 2021.01.19 |