14. Hash1 + IDX Str arr 1

 

문제 접근

사실 문제를 어떻게 풀지 알맞은 방법으로 접근하는 것이, 이 문제의 핵심이였다고 볼수있다. 정말 많은 방법이 있다. Trie를 사용하는 방법, *을 중심으로 앞뒤로 hash를 두는 방법, 그리고 내가 사용한 방법인 *포함한 모든 가능성있는 글자를 하나의 hash로 두는 방법이다.

시간 속도 차이를 보면, Trie보다는 hash가 빠르고 hash 중에서는 어떻게 짜냐에 따라서 살짝식 바뀐다.

 

어려웠던 점

flag라는 글자가 있을때

flag,

*flag, *lag, *ag, *g, *

f*lag, f*ag, f*g, f*

fl*ag, fl*g, fl*

fla*g, fl*

flag*

이렇게 나눠서 hash로 넣어야하는데 그 3중 for문을 짜는 것이 그렇게 어려운건 아닌데,, 나름 애를 먹었다.

코드로 보면 다음과 같다.

 

void addWord(char str[]) {
	// 기존 name hash 설정
	int key = getkey(str);
	int nowaidx, nowcidx;
	nowaidx = aidx++;
	if (hash[key].next == 0) {
		hash[key].cnt = 1;
		nowcidx = cidx++;
		
		hash[key].cidx = nowcidx;
		mstrcpy(wname[nowcidx], str);
		buf[bfcnt++].alloc(nowaidx, hash[key].next, &hash[key]);
	}
	else {
		hash[key].cnt++;
		buf[bfcnt++].alloc(nowaidx, hash[key].next, &hash[key]);
	}

	// wildcard name hash 설정
	int len = mstrlen(str);
	register int k = 0, cnt;
	char wnameTmp[8];
	for (register int i = 0; i < len; i++) {
		for (register int j = 0; j < len && (j+i)<=len; j++) {
			cnt = 0;
			int flag = 1;
			for (k = 0; k < len; k++) {
				if (i == k && flag) {
					flag = 0;
					k += j;
					k -= 1;
					wnameTmp[cnt++] = '*';
				}
				else {
					wnameTmp[cnt++] = str[k];
				}
			}
			wnameTmp[cnt] = '\0';
			add(wnameTmp, nowaidx);
		}
	}

	// arr설정
	mstrcpy(arr[nowaidx].name, str);
	arr[nowaidx].del = 0;

	// 추가 저장
	wnameTmp[0] = '*';
	wnameTmp[1] = '\0';
	add(wnameTmp, nowaidx);
	mstrcpy(wnameTmp, str);
	wnameTmp[len++] = '*';
	wnameTmp[len++] = '\0';
	add(wnameTmp, nowaidx);
	
}

 

실수

이 문제에서의 실수는 이 부분이다.

 

int getkey(char str[]) {
	int key = 0;
	for (register int i = 0; str[i]; i++) key = (key * 32 + str[i])%HSIZE;
	while (hash[key].next != 0 && mstrcmp(wname[hash[key].cidx],str)!=0) {
		key++;
		key %= HSIZE;
	}
	return key;
}

 

저기서 mstrcmp(wname[hash[key].cidx],str)!=0 으로 안 하고,

mstrcmp(wname[hash[key].cidx],str)==0 으로 하는 바람에 살짝 고생했다.

소스코드

#define HSIZE 900001 // 30000만 있어도 될거같기도 함
#define ADDMAX 50001
int mstrcmp(const char a[], const char b[]) {
	int i;
	for (i = 0; a[i] != '\0'; ++i) if (a[i] != b[i]) return a[i] - b[i];
	return a[i] - b[i];
}
void mstrcpy(char dest[], const char src[]) {
	int i = 0;
	while (src[i] != '\0') { dest[i] = src[i]; i++; }
	dest[i] = src[i];
}
int mstrlen(const char a[]) {
	int i;
	for (i = 0; a[i] != '\0'; ++i);
	return i;
}
struct Hash {
	int aidx, cidx, cnt;
	Hash* next, * prev;
	void alloc(int _aidx, Hash* _next, Hash* _prev) {
		aidx = _aidx; next = _next, prev = _prev;
		if (next) next->prev = this;
		if (prev) prev->next = this;
	}
	void pop() {
		if (next) next->prev = prev;
		if (prev) prev->next = this;
	}
}hash[HSIZE],buf[ADDMAX*10];
struct Arr {
	char name[7];
	int del;
}arr[ADDMAX];
char wname[ADDMAX * 10][8];
int bfcnt, aidx, cidx;
int getkey(char str[]) {
	int key = 0;
	for (register int i = 0; str[i]; i++) key = (key * 32 + str[i])%HSIZE;
	while (hash[key].next != 0 && mstrcmp(wname[hash[key].cidx],str)!=0) {
		key++;
		key %= HSIZE;
	}
	if (key == 111459) {
		int d = 0;
	}
	return key;
}