14425 - 문자열 집합 (Hash 풀이)

https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

 

Trie로 풀었던 문제를 Hash로 풀어봅시다.

 

Hash는 뭐 다들 아시죠? 제가 미리 올려놓은 그 코드를 확인하시면 될 거 같습니다.

아래에서 다룬 것과 완전 똑같아요. 충돌처리도 했습니다 !

 

https://ggodong.tistory.com/161

12791 - Starman

#include <stdio.h>
#include <malloc.h>

#define MAX_TABLE_SIZE 10000000

typedef struct _node {
	char key[501];
	struct _node* next;
} Node;

typedef struct _dic {
	struct _node* head;
}Dic;

Dic dict[MAX_TABLE_SIZE];

int N, M, result = 0;
char word[501];

int hashing(char* word) {
	int hash = 5031, idx = 0;
	while (word[idx] != '\0') {
		hash = (((hash << 5) + hash) * (int)word[idx]) % MAX_TABLE_SIZE;
		idx++;
	}
	if (hash < 0) return (hash % MAX_TABLE_SIZE) * -1;
	return hash % MAX_TABLE_SIZE;
}

Node* makeNode() {
	Node* node = (Node*)malloc(sizeof(Node));
	node->next = NULL;
	return node;
}

void my_strcpy(char* str1, char* str2) {
	int idx = 0;
	while (str2[idx] != '\0') {
		str1[idx] = str2[idx];
		idx++;
	}
	str1[idx] = '\0';
}

void insert(char* word) {
	int hash = hashing(word);
	Node* tmp = makeNode();
	my_strcpy(tmp->key, word);
	if (!dict[hash].head) dict[hash].head = tmp;
	else {
		Node* cur = dict[hash].head;
		while (cur->next) cur = cur->next;
		cur->next = tmp;
	}
}

int strcmp(char* str1, char* str2) {
	int idx1 = 0, idx2 = 0;
	while (str1[idx1] != '\0') idx1++;
	while (str2[idx2] != '\0') idx2++;

	if (idx1 != idx2) return 0;

	for (int i = 0; i < idx1; i++) {
		if (str1[i] != str2[i]) return 0;
	}
	return 1;
}

int find(char* word) {
	int hash = hashing(word);
	Node* cur = dict[hash].head;
	if (!cur) return 0;
	else {
		while (cur) {
			if (strcmp(cur->key, word)) return 1;
			else {
				cur = cur->next;
			}
		}
		return 0;
	}
}

int main(void) {
	scanf("%d %d", &N, &M);
	// N
	for (int n = 0; n < N; n++) {
		scanf("%s", word);
		insert(word);
	}
	// M
	for (int m = 0; m < M; m++) {
		scanf("%s", word);
		if (find(word)) result++;
	}
	printf("%d", result);
}

확실히 Trie 풀이보다 자원도 절약되고 시간도 절약되는 좋은 문제 풀이 방법이었습니다.

근데 참 이상한게

int hashing(char* word) {
	int hash = 5031, idx = 0;
	while (word[idx] != '\0') {
		hash = (((hash << 5) + hash) * (int)word[idx]) % MAX_TABLE_SIZE;
		idx++;
	}
	if (hash < 0) return (hash % MAX_TABLE_SIZE) * -1;
	return hash % MAX_TABLE_SIZE;
}

해시를 했던 이 부분에서 Shift 연산은 5로 걸었는데요.

 

이걸 그냥 2로 해볼까 해서 2로 바꾸니 시간초과가 떴습니다 !!!!

이건 진짜 왜 이럴까요..?

 

아마 제 생각엔 충돌이 많이나서 해시에서 원하는 값을 찾고 싶을 때 뜻 대로 되지 않아서 시간이 오래 걸리는 거 같습니다.

 

정말 무섭군요 해시... 마치 양날의 검과 같은

 

덜덜

 

그러니 우리 모두 숫자 5를 사랑합시다.

---

이상 14425 - 문자열 집합 (Hash)였습니다. ^_^