글 읽기 - 런타임에러 발생합니다.

mmx3d1234 4년 전 0

런타임에러가 발생하는데 원인을 모르겠습니다.

#include <stdio.h>


struct Node
{
	bool finish;
	Node *number[10];
}DUT[10000];

int arridx = 0;


Node *myalloc()
{
	for (int i = 0; i < 10; i++)
		DUT[arridx].number[i] = NULL;
	DUT[arridx].finish = false;

	return &DUT[arridx++];
}

int ADD(Node *root, char *str)
{
	Node *c = root;
	int i = 0;
	int ret = 0;
	while (str[i] != '\0')
	{
		int idx = str[i] - '0';

		if (c->number[idx])
		{
			c = c->number[idx];
			if (c->finish)
				ret = 1;
		}
		else
		{
			Node *newNode = myalloc();
			c->number[idx] = newNode;
			c = c->number[idx];
		}
		i++;
	}

	c->finish = true;

	return ret;
}

int main()
{
	int testcase;
	scanf("%d", &testcase);

	for (int t = 0; t < testcase; t++)
	{
		arridx = 0;
		int n;
		int ret = 0;
		scanf("%d", &n);

		char phoneNumber[11];
		Node *root = myalloc();
		for (int i = 0; i < n; i++)
		{
			scanf("%s", &phoneNumber);

			if (!ret)
				if (ADD(root, phoneNumber))
					ret = 1;
		}

		if (ret)
			printf("NO\n");
		else
			printf("YES\n");
	}



	return 0;
}

chogahui05 4년 전 0

Trie를 구현해 놓고 그 주솟값을 배열에 저장해 놓으신 것 같은데요. 제가 트라이 짤 때 메모리 해제하기 귀찮아서 쓰던 방식인데.. ㅎㅎ

Trie는 문자의 총 갯수만큼 할당이 되어요.

일단 한 전화번호당 나올 수 있는 문자의 수는 최대 10개이고, 전화번호 수는 10^4개인데

10^4개의 노드 주소만 가지고 있겠다는 건 무리수죠. 최소한 10^5 이상 선언해 주시고요.

그리고 알고리즘 구조상

ABC

ABCDE

는 잘 판단하겠지만

ABCDE

ABC

는 판단하지 못할겁니다.

왜냐하면 ABCD(E)에서 끝났는데

다음에 ABC가 들어왔을 때, 탐색하는 과정에서 Term이 아니기 때문에, 한 번호가 다른 번호의 접두어가 아니다. 라고 판단을 하는데

실제로는 ABC는 ABCDE의 접두어입니다. 그러면 어떻게 판단해야 할 지 잘 생각해 보세요.

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

문제

문제

출처

ICPC

런타임에러 발생합니다.

mmx3d1234 4년 전 0

chogahui05 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말