글 읽기 - 듣보잡 문제 런타임에러 도저히 영문을 모르겠습니다.

dustn9401 6년 전 0

일단 해시테이블에 듣도 못한 사람의 명단을 넣고

보도 못한 사람을 테이블에서 검색하여 테이블에 존재하면 결과를 저장하는 배열인 res에 넣는 방식으로 만들어 봤습니다.

그런데 런타임 에러가 떠 버렸습니다............ 이름도 널문자까지 고려하여 21크기의 배열로 잡았고, 정답이 50만 개 일 경우를 고려하여

듣도 보도 못한 놈을 저장하는 배열의 크기도 50만 으로 하였습니다......

도대체 어디서 문제가 생기는 것인지 도무지 모르겠어서 질문 올립니다...

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_BUCKET 500000
typedef struct node {
	char str[21];
	struct node *next;
}node;
int n, m;
node *table[MAX_BUCKET];
char res[500000][21], res_idx = 0;
int hash(char *name) {    //해시 함수 입니다.
	int key = 0;
	while (*name)
		key = (key * 31 + *name++) % MAX_BUCKET;
	return key;
}
void init() {    //해시 테이블 초기화 입니다.
	for (int i = 0; i < MAX_BUCKET; i++)
		table[i] = NULL;
}
void insert(char *name) {    //해시 테이블 삽입 함수입니다. 듣도 못한 놈을 저장합니다.
	node *n = (node *)malloc(sizeof(node));
	int idx = hash(name);
	n->next = table[idx], strcpy(n->str, name);
	table[idx] = n;
}
int seek(char *name) {    //해시 테이블에서 보도 못한 놈을 검색하여 찾으면 1을 반환합니다.
	int idx = hash(name);
	for (node *i = table[idx]; i; i = i->next) {
		if (strcmp(name, i->str) == 0)
			return 1;
	}
	return 0;
}
int comp(const void *a, const void *b) {    //qsort를 위한 비교함수 입니다.
	return strcmp((char *)a, (char *)b);
}
int main()
{
	init();
	scanf("%d%d", &n, &m);
	char str[21];
	for (int i = 0; i < n; i++) {    //듣도 못한 놈 입력
		scanf("%s", str);
		insert(str);
	}
	for (int i = 0; i < m; i++) {    //보도 못한 놈 입력
		scanf("%s", str);
		if (seek(str))
			strcpy(res[res_idx++], str);    //보도 못한 놈이 테이블에 존재하면 결과 배열에 저장
	}
	qsort(res, res_idx, sizeof(res[0]), comp);    //사전순 정렬
	printf("%d\n", res_idx);
	for (int i = 0; i < res_idx; i++)
		printf("%s\n", res[i]);
	return 0;
}

chogahui05 6년 전 0

어떤 것 때문에 런타임이 뜨는지는.. 흐음.. 자세히 안 봤지만요.

제가 봤을 때는 insert 과정에서.. 끝에 null을 안 붙여서

seek 과정에서 런타임 뜨는 거 같은데요.

24번째 줄에서 hash 값을 얻어와요. 이걸 버킷에다가 넣잖아요.

그게 table[idx] = n;

이 문장인 거 같은데요.

만약에 해당 버킷에 단 1개의 원소만 추가되었다면 어떤 일이 벌어지나요?

제가 봤을 때는

사이클이 생겨서 무한루프 돌 거 같은데요.

차라리 head와 tail 포인터를 둬서 따로 관리하시는 게 좋을 거 같네요.

chogahui05 6년 전 1

malloc으로 생성한 것은 힙에 할당되기도 하고요..

초기화 될 때 랜덤한 값으로 되어버려요. 그렇기 때문에 next 같은 경우도 초기화를 안 해주면

이상한 어느 공간을 가르키고 있겠죠..

링크드 리스트 같은 경우.

새 노드를 할당한 다음에 끝에 추가하는 경우 next에 null을 할당시켜버리는 게 보통입니다.

dustn9401 6년 전 0

답글 감사합니다. 참고해서 해보겠습니다

dustn9401 6년 전 0

혹시 조금만 더 자세히 설명 해 주실 수 있으신가요..?ㅠㅠ

처음에 모든 헤드를 NULL로 초기화 하고 새로 들어오는 데이터는 무조건 헤드 앞에 넣어서

리스트의 마지막 데이터는 항상 NULL을 가리키게 하였는데...

무한 루프가 돌 수가 있는지요..ㅠㅠ

//phead는 이미 NULL로 초기화 되어있는 상태
if(phead == NULL){
    new_node->link == NULL;
    phead = new_node;
}
else{
    new_node->link = phead;
    phead = new_node;
}
//위의 코드와...
new_node->link = phead;    
phead = new_node;
//위의 코드가 같은 것이 아닌지요??ㅠㅠ

chogahui05 6년 전 0

링크드 리스트 먼저 구현해 보시는 게 좋아보입니다..

경험이 없으면 어려울 수도 있어서요..

dust님의 의도대로 하시려면 먼저

Bucket[uu] = null로 초기화를 먼저 해 놓고요.

아마 이 경우 Bucket[uu]의 head도 null이겠죠??

만약에 이 값이 null인 경우

새로 hashcode가 uu인 데이터가 들어왔을 경우 (주소가 new_node일 경우)

Bucket[uu] = new_node; new_node->next = null; 이렇게 초기화를 해 주시면 되겠네요..

Bucket[uu].head = new_node가 될 거고요.

만약에 이미 Bucket[uu]에 데이터가 있을 경우..

new_node -> next = Bucket[uu]가 될 거고요.

Bucket[uu] = new_node 이래 하시면 될 거 같네요..

끝에 붙어있는 노드가 null이 아니라면 무한 루프를 돌아버릴 수 있어요~

그림을 그려보시면서 천천히 구현해 보세요.

chogahui05 6년 전 0

의도대로 구현하시려면 이런 식으로 구현하시는 게 맞아보입니다.

new_node = (~)malloc(sizeof(~));

new_node -> data = ??

new_node -> next = NULL;

if(Bucket[~]==NULL)

{

Bucket[~] = new_node;

}

else

{

new_node -> next = Bucket[~];

Bucket[~] = new_node;

}

dustn9401 6년 전 0

해결했습니다. 처음에 res_idx가 char로 선언되어있는데 int로 바꾸니 됬습니다.

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

문제

문제

출처

ICPC

듣보잡 문제 런타임에러 도저히 영문을 모르겠습니다.

dustn9401 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 1

dustn9401 6년 전 0

dustn9401 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

dustn9401 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말