글 읽기 - 해시 테이블을 이용한 후 명단을 소팅 했는데 메모리 초과가 납니다.

vvv3334 5년 전 0

해시 테이블을 이용해서 풀엇는데 100%에서 메모리 초과가 납니다.

같은 방식으로 quicksort는 메모리 초과가 안나고 통과했는데, merge sort는 메모리가 초과가 되네요..

왜 이런걸까요 ㅠㅠ

#include <stdio.h>
#define MAX_TABLE (10007)

typedef long long int ll;
int N, M;

typedef struct st
{
	char name[21];
	struct st *next;
}HASH;

HASH Hash[MAX_TABLE + 100];
HASH POOL[500001];
int cnt;

void strcpy(char *a, char *b)
{
	while (*a++ = *b++);
}

int strcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

ll hash(const char *str)
{
	ll hash = 5381;
	int c;

	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}

	return hash % MAX_TABLE;
}

char* a[500001];
char* b[500001];
int listcnt;

void merge(int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) / 2;
	i = start;
	j = mid + 1;
	k = 0;

	while (i <= mid && j <= end)
	{
		if (strcmp(a[i], a[j]) < 0) b[k++] = a[i++];
		else b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];
	for (i = start; i <= end;i++)
		a[i] = b[i - start];

}

void sort(int start, int end)
{
	int mid;
	if (start == end) return;

	mid = (start + end) / 2;
	sort(start, mid);
	sort(mid + 1, end);
	merge(start, end);
}

int main(void)
{
	int i;
	ll h;
	HASH *nd;
	char str[21];

	scanf("%d %d", &N, &M);

	for (i = 0; i < N;i++)
	{
		scanf("%s", str);
		h = hash(str);

		nd = &POOL[cnt++];
		strcpy(nd->name, str);

		nd->next = Hash[h].next;
		Hash[h].next = nd;
	}

	for (i = 0; i < M;i++)
	{
		scanf("%s", str);
		h = hash(str);

		for (nd = Hash[h].next; nd; nd = nd->next)
		{
			if (!strcmp(nd->name, str))
				a[listcnt++] = nd->name;
		}
	}

	sort(0, listcnt - 1);

	printf("%d\n", listcnt);
	for (i = 0; i < listcnt;i++)
		printf("%s\n", a[i]);

	return 0;
}

djm03178 5년 전 1

듣보잡이 단 한 명도 없을 경우, sort(1, 0)이 무한히 재귀호출됩니다.

vvv3334 5년 전 0

감사합니다.. ㄷㄷ 오늘도 새로운걸 배워가네요!!

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

문제

문제

출처

ICPC

해시 테이블을 이용한 후 명단을 소팅 했는데 메모리 초과가 납니다.

vvv3334 5년 전 0

djm03178 5년 전 1

vvv3334 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말