hash table을 구현해 보자

이제 학교에서 해우면서 PS에서 사용하는 자료구조 포스팅은 이게 아마 마지막일듯 싶다.

Q. ??? 너는 학교에서 rb-tree도 안배움??
A. 배웠다. 근데 못짠다. 그리고 PS에서 실제 구현하는 사람이 있을까 싶다.... 우리는 map이 있자나!!!! 그리고 내가 rb-tree를 못짜고 map을 사용하는 방법도 모르기에 hash table을 구현해서 문제를 비벼오고 있다.

Q. 이글에선 충돌 어떻게 처리할거임?
A. chaning이다. 어짜피 open addressing 혹은 double hahsing 해서 돈고쇼 한다해도 여러분은 chaning만 볼꺼잔슴... ㅠㅠ

Q. 이거 바로 읽어도 됨??
A. 이글, 저글 그리고 요글을 읽고 오도록 하자. 읽고 왔으면 느낌이 올거다. '아... 21.. 또 연결리스트로 만들겠네....' 정답.

당연히 문제를 통해서 검증을 할것이다. 오늘의 문제는 이거다!

Q. 아 ㅋㅋㅋㅋㅋ 이런 문제에 hash table을 태워??
A. 아 ㅋㅋㅋㅋㅋ 잠시 변명 time을 가지자.

  1. 나는 내가 ac받은 코드 전체를 올릴예정이다. 근데 너도 알다싶이 백준은 test case추가가 가능하고 hash table은 저격이 충분히 가능하다. 혹시 누가 test case 추가라고 한다면? 난 다시 짜야한다. 그래서 아무리 test case를 추가해도 안터지는 그런 문제를 준비했다.
  2. 그리고 문제 푸는데에 있어서 아무 지장이 없다 ㅎ..

각설하고 그림부터 보자.

1-3

초기 그림이다. 참고로 나는 queue를 사용 할 것이다. 그러므로 내가 이전에 링크를 건 글을 읽고오는 것을 추우천

여기서 우리는 숫자 하나를 입력받고 key값을 받았는데 그 key값이 3이라고 해보자.

2-3

그러면 이제 search함수에 key값과 num값을 통해 이전에 num이라는 숫자가 이미 저장대었는지 확인해보자.

struct info search(int key, int num)
{
	struct info ret;
	struct node* temp;
	for (temp = f[key], ret.s = 0; temp; temp = temp->next)
	{
		if (table[temp->idx].num == num)
		{
			ret.s = 1;
			ret.i = temp->idx;
			break;
		}
	}
	return ret;
}

search함수는 이런 모양인데 temp는 이미 시작부터 NULL이니 ret.s = 0, ret.i = ? 인 상태로 return 된다.

그럼 push와 save함수를 실행한다. push함수는 queue의 글의 push와 같다. 실행한 그림을 보자

3-4

보면 알겠지만 queue에는 num을 저장하는 것이 아닌 num에 대한 정보가 저장대어있는 table의 index를 저장한다.

이제 save함수를 호출하는데 호출 후 상황을 그림으로 보자

4-4

이런 그림이 된다.
여기서 다시한번 숫자를 입력받고 key값을 받았는데 또 key값이 3이라 가정해보자.

5-3

여기서 또 search함수를 실행해보자.

6-2

같은 key값을 가지지만 num과 num1은 같지 안기에 이전과 같이 ret.s = 0, ret.i = ? 인 상태로 return 된다.

이전과 마찬가지로 push와 save함수를 콜해서 아래와 같은 상태가 된다.

7-4

자 이제 다 돼간다....

다음 숫자를 받았는데 다시 한번 num2가 입력이 된 상태이다. 그럼 마찬가지로 key값이 3일 것이다.

8-4

이때 search함수를 콜해보자.

9-2

처음 search에는 같지 않다. 다음을 보자

10-4

같은 숫자를 찾아낸 상태이다. 이때는 ret.s = 1, ret.i = 1인 상태로 return이 된다.
여기서 ret.i는 table의 index가 되겠다.

그럼 우리는 찾았으니 modi함수에 flag.i의 값을 넘겨서 콜해보자.

11-2

이런 상태가 될 것이다.

흐아 다 끝났다. 그래서 마지막 답은 어케 찾냐구?

scanf("%d", &num);
key = get_key(num);
flag = search(key, num);
return flag.s ? table[flag.i].cnt : 0;

이거지뭐 ㅋㅋ

Q. hash func은?
A. '운'이라고 생각한다.

Q. 꼭 queue로만 해야하나?
A. 아니 나는 queue랑 double linked list이 두가지를 주로 사용한다.
그래서 내가 사전에 읽어야 할 글 링크를 걸어둔 것이다. 사실 witch의 구현이랑은 조금 다르지만 뭐 본인 입맛대로 구현하는 거기에 본인에게 맡겨두겠다.

이제 당분간은 구현 포스팅은 할일 없지 싶다. 후아.


출처 : https://www.acmicpc.net/problem/10807

아래 코드는 위 링크의 나의 풀이코드 이다.
나도 안다. 이렇게 안풀어도 된다는거.

#include<stdio.h>
#include<malloc.h>
#define hsize 1351
struct node
{
	int idx;
	struct node* next;
};
struct info
{
	int s, i;
};
struct data
{
	int num, cnt;
};
struct node* f[hsize], * r[hsize];
struct data table[100];
int answer, tidx;
int get_key(int);
struct info search(int, int);
void push(int, int);
void save(int);
void modi(int);
struct node* get_node();
void fin();
struct node pop(int);
int make_answer();
int main(void)
{
	answer = make_answer();
	printf("%d\n", answer);
	fin();
	return 0;
}
int make_answer()
{
	int i, n, num, key;
	struct info flag;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &num);
		key = get_key(num);
		flag = search(key, num);
		if (!flag.s)
		{
			push(key, tidx);
			save(num);
		}
		else
		{
			modi(flag.i);
		}
	}
	scanf("%d", &num);
	key = get_key(num);
	flag = search(key, num);
	return flag.s ? table[flag.i].cnt : 0;
}
int get_key(int num)
{
	return (num > 0 ? num : num * -1) % hsize;
}
struct info search(int key, int num)
{
	struct info ret;
	struct node* temp;
	for (temp = f[key], ret.s = 0; temp; temp = temp->next)
	{
		if (table[temp->idx].num == num)
		{
			ret.s = 1;
			ret.i = temp->idx;
			break;
		}
	}
	return ret;
}
void push(int key, int idx)
{
	struct node* temp;
	temp = get_node();
	temp->idx = idx;
	temp->next = 0;
	if (!f[key])
	{
		f[key] = temp;
	}
	else
	{
		r[key]->next = temp;
	}
	r[key] = temp;
}
struct node* get_node()
{
	return (struct node*)malloc(sizeof(struct node));
}
void save(int num)
{
	table[tidx].num = num;
	table[tidx++].cnt = 1;
}
void modi(int idx)
{
	table[idx].cnt++;
}
void fin()
{
	int i;
	for (i = 0; i < hsize; i++)
	{
		while (f[i])
		{
			pop(i);
		}
	}
}
struct node pop(int key)
{
	struct node* temp, ret;
	temp = f[key];
	ret = *f[key];
	f[key] = f[key]->next;
	free(temp);
	return ret;
}

다들 시험 잘치길 바란다.

12-2