글 읽기 - 해쉬로 풀었을때 시간초과에 대한 질문입니다.

rjs463 5년 전 0

시간초과가 나오는 이유를 아무리 생각해도 찾을 수가 없습니다. 살려주세요.. 절실합니다.

해쉬로 풀고자 하였습니다. 포켓몬 이름을 해쉬함수로 돌려서 해쉬 테이블에 넣었고, 이름에 해당하는 번호를 저장하는 배열을 만들어 약간은 가라로 짰긴 했습니다만 시간 초과가 왜 나오는지 아무리봐도 이해가 되지 않습니다. 고수님들 도와주세요..

#include <stdio.h>

#define MAX_SIZE 1000001

void StrCpy(char a[], char b[]){
	int i = 0;
	while (b[i] != '\0'){
		a[i] = b[i];
		i++;
	}
	a[i] = '\0';
}
int Stoi(char a[]){
	int i = 0;
	int res = 0;
	while (a[i] != '\0'){
		res = (res * 10) + (a[i] - '0');
		i++;
	}
	return res;
}
int StrCmp(char a[], char b[]){
	int i = 0;
	while (a[i] != '\0' && b[i] != '\0'){
		if (a[i] != b[i]) return false;
		i++;
	}
	return true;
}


struct NODE{
	char name[21];
	int num = 0;
	NODE* prev;
}a[100000];


//포켓몬 번호를 저장하기 위한 배열
char arr[100000][21];



int arr_idx = 0;
//할당
NODE* myalloc(void){
	return &a[arr_idx++];
}


//해쉬 테이블
NODE* hTable[MAX_SIZE];


//해쉬함수
unsigned long myhash(const char *str){
	unsigned long hash = 100003;
	int c;

	while (c = *str++){
		hash = (((hash << 5) + hash) + c) & MAX_SIZE;
	}
	return hash % MAX_SIZE;
}

int main(void){
	//freopen("input.txt", "r", stdin);
	int p, q;
	scanf("%d %d", &p, &q);
	arr_idx = 0;
	NODE *b;
	int key;
	char in[22];
    
    
    
    //포켓몬을 해쉬테이블에 넣습니다.
	for (register int i = 0; i < p; i++){
		scanf("%s", in);
		key = (int)myhash(in);
		b = myalloc();
		b->num = arr_idx;
		StrCpy(arr[arr_idx], in);
		StrCpy(b->name, in);
		b->prev = hTable[key];
		hTable[key] = b;
	}


    
    //해쉬 테이블에 있는 값을 가져오거나 번호일 시 저장된 배열에서 가져옵니다.
	for (register int i = 0; i < q; i++){
		scanf("%s", in);
		if (in[0] >= '0' && in[0] <= '9'){
			int res = Stoi(in);
			printf("%s\n", arr[res]);

		}
		else{
			key = (int)myhash(in);
			for (NODE * pp = hTable[key]; pp != NULL; pp = pp->prev){
				if (StrCmp(in, pp->name)){
					printf("%d\n", pp->num);
					break;
				}
			}
		}
	}

}

61번째 줄에 보면 마지막에 & MAX_SIZE를 하는데, 이 때문에 hash가 가질 수 있는 값은 MAX_SIZE를 이진수로 표현했을 때 1인 자릿수의 개수에 따라 결정됩니다. 1000001은 이진수로 11110100001001000001, 즉 1이 8개이기 때문에 2^8=256가지 값밖에 나타내지 못하고, 이 때문에 서로 다른 이름끼리 key가 겹치는 일이 매우 많아지게 됩니다. 그래서 탐색에 매우 오랜 시간이 걸립니다.

& MAX_SIZE만 지우면 맞습니다.

jh05013 5년 전 0

% MAX_SIZE를 의도하셨나 보군요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

해쉬로 풀었을때 시간초과에 대한 질문입니다.

rjs463 5년 전 0

djm03178 5년 전 1

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말