글 읽기 - 반례가 궁금합니다.

lonnie123 1년 전 0

해시 테이블을 이용해 처음 입력 받은 문자열들을 저장하고 이후 입력 받는 문자열들에 대해 해당 문자열이 해시 테이블에 존재하는지 검색, 해시 테이블에 존재하는 경우 새로운 배열에 저장, 정렬(qsort)하여 출력하는 방식으로 코드를 설계했습니다. 질문 게시판에 존재하는 반례들에 대해선 문제 없이 잘 작동하는데, 정작 해당 코드를 제출하면 출력 초과가 뜹니다. 어떤 부분에 문제가 있어 해당 오류가 발생하는 것인지 알고 싶습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Tablesize 700001

char* trash;
char* card[Tablesize] = { trash, };

int Hash(char* Key) {
	int Keylen = strlen(Key);
	int Hashvalue = 0;
	for (int i = 0; i < Keylen; i++) Hashvalue += Key[i];
	return Hashvalue;
}
int Hash1(char* Key) {
	int Hashvalue = Hash(Key);
	return Hashvalue % Tablesize;
}
int Hash2(char* Key) {
	int Hashvalue = Hash(Key);
	return Hashvalue % (Tablesize - 7) + 1;
}
void Addtable(char* Key) {
	int Address = Hash1(Key);
	int Stepsize = Hash2(Key);
	while (card[Address] != trash) Address = (Address + Stepsize) % Tablesize;
	card[Address] = Key;
}
int Gettable(char* Key) {
	int Address = Hash1(Key);
	int Stepsize = Hash2(Key);
	while (card[Address] != trash) {
		if (*card[Address] == *Key) return 1;
		Address = (Address + Stepsize) % Tablesize;
	}
	return 0;
}

char List[500000][21];
int compare(const void* a, const void* b) {
	return strcmp((const char*)a, (const char*)b);
}

int main() {
	int N, M, i, check, count = 0;
	char temp[21];
	scanf("%d%d", &N, &M);
	for (i = 0; i < N; i++) {
		scanf("%s", temp);
		Addtable(temp);
	}
	for (i = 0; i < M; i++) {
		scanf("%s", temp);
		check = Gettable(temp);
		if (check == 1) {
			count += 1;
			strcpy(List[count - 1], temp);
		}
	}
	qsort(List, count, sizeof(*List), compare);
	printf("%d\n", count);
	for (i = 0; i < count; i++) {
		printf("%s\n", List[i]);
	}
}

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

문제

문제

출처

ICPC

반례가 궁금합니다.

lonnie123 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말