글 읽기 - TRIE 로 풀었는데, 어디서 틀린걸까요..?

qptnnm 2년 전 0

linked list로 구현을 했고, link로 0~9까지의 숫자 10개만큼 두었습니다.

head를 제외한 각 노드마다 글자를 하나씩 두었고, 입력한 전화번호의 마지막 문자에는 isEnd = true로 두었습니다.

전화번호를 추가할 때마다 노드를 탐색하다가 isEnd를 만나면 false를 return하도록 하였습니다.

제출하면 Fail이 나는데, 어디가 틀렸는지 알려주실 수 있나요?

아니면 실패 예제를 알려주시면 감사드리겠습니다 ㅠㅠ

#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#define NULL 0
#define _CRT_SECURE_NO_WARNINGS 

typedef struct trie
{
	char data;
	bool isEnd;
	struct trie* link[10];
	
} TRIE;

TRIE* head;
int T, N;

int strlen(char* str) {
	int len = 0;
	while (str[len] != '\0')
		len++;
	return len;
}
bool addNumber(char* number);
void initializeLink(TRIE* cur, int no);
void initPtr(TRIE* cur);

int main() {
	scanf("%d", &T);
	for (int i = 0; i < T; i++)	{
		bool ret = true;
		head = (TRIE*)malloc(sizeof(TRIE));
		initPtr(head);
		scanf("%d", &N);

		for (int i = 0; i < N; i++) {
			char number[10];
			scanf("%s", number);
			ret &= addNumber(number);
		}
		if (ret) {
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
	
	return 0;
}

void initPtr(TRIE* cur) {
	cur->data = '-';
	cur->isEnd = false;
	for (int i = 0; i < 10; i++) {
		cur->link[i] = NULL;
	}
}

void initializeLink(TRIE* cur, int no) {
	cur->link[no] = (TRIE*)malloc(sizeof(TRIE));
	initPtr(cur->link[no]);
	
}

bool addNumber(char* number) {
	TRIE* cur = head;
	bool ret = true;
	for (int i = 0; i < strlen(number); i++)
	{
		int no = (int)number[i] - 48;
		if (cur->link[no] == NULL) {
			initializeLink(cur, no);
			cur = cur->link[no];
			cur->data = no;

			if (i == strlen(number) - 1)
				cur->isEnd = true;
		}
		else if (cur->link[no]->isEnd == true) {
			ret = false;
			break;
		}
		else {
			cur = cur->link[no];
		}
	}
	return ret;
}

gaelim 2년 전 5

반례 데이터입니다.

91125426

911

97625999

qptnnm 2년 전 0

감사합니다 !

해당 케이스를 전혀 생각지 못하고 있었네요ㅠㅠ 덕분에 하나 더 배워갑니다 !

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

문제

문제

출처

ICPC

TRIE 로 풀었는데, 어디서 틀린걸까요..?

qptnnm 2년 전 0

gaelim 2년 전 5

qptnnm 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말