글 읽기 - C99 16%에서 자꾸 틀립니다. 한번만 시간 내주시면 감사하겠습니다.

hse07088 1년 전 0

본 문제를 hashtable을 작성해서 풀어보려고 하였는데, 예제나 제가 임의로 작성한 데이터들에 대해서는 모두 정답이 출력되나 제출해보면 16%에서 자꾸 틀렸다고 뜹니다.. 반례를 도저히 못 찾겠어서 질문 올려봅니다.. 도와주시면 정말 감사하겠습니다. ㅠㅠㅠ

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int N, M;
char Dic[100005][24];

struct Mon{
	int num;
	char* name;
	struct Mon* next;
};

struct Bucket {
	struct Mon* mon;
};

struct Bucket* dict=NULL;

struct Mon* createMon(int num, char *name) {
	struct Mon* newnode;
	newnode = (struct Mon*)malloc(sizeof(struct Mon));
	newnode->num = num;
	newnode->name = (char*)malloc(sizeof(char)*(strlen(name)+1));
	strcpy(newnode->name, name);
	newnode->next = NULL;
	return newnode;
}

int hash(char *name) {
	int result = 0;
	int len = strlen(name);
	for (int i = 0; i<len; i++) {
		result = (result*123+ name[i])%(2*N);
	}
	return result;
}

void insert(int num, char* name) {
	int idx = hash(name);
	struct Mon *new = createMon(num, name);
	if (dict[idx].mon == NULL) {
		dict[idx].mon = new;
	}
	else {
		new->next = dict[idx].mon;
		dict[idx].mon = new;
	}
	return;
}

int search(char *name) {
	int idx = hash(name);
	struct Mon* mon = dict[idx].mon;
	while (mon != NULL) {
		if (strcmp(mon->name, name) == 0) {;
			return mon->num;
		}
		mon = mon->next;
	}
	return;
}

int main(void) {
	scanf("%d %d", &N, &M);
	char na[25], key;
	dict = (struct Bucket*)malloc(N * sizeof(struct Bucket)*2);
	memset(dict, 0, N * sizeof(struct Bucket) * 2);
	for (int i = 1; i <= N; i++) {		
		scanf("%s", na);
		strcpy(Dic[i], na);
		insert(i, na);
	}
	int len;
	for (int i = 1; i <= M; i++) {
		scanf("%s", na);
		key = 0;
		len = strlen(na);
		if (na[0] < 65) {
			for (int j = 0; j < len ; j++) {
				key = key * 10 + na[j]-48;
			}
			printf("%s\n", Dic[key]);
		}
		else {
			printf("%d\n", search(na));
		}
	}
	return 0;
}

djm03178 1년 전 1

key가 char형으로 선언되어 있어 127까지의 수밖에 표현하지 못합니다. int로 바꾸어주면 맞습니다.

hse07088 1년 전 0

감사합니다.. 감사합니다.....

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

문제

문제

출처

ICPC

C99 16%에서 자꾸 틀립니다. 한번만 시간 내주시면 감사하겠습니다.

hse07088 1년 전 0

djm03178 1년 전 1

hse07088 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말