글 읽기 - 제 풀이에 대해 질문드립니다.

sjlee0218 2년 전 0

저는 문자열을 입력받아서 트라이에서 접두사로 찾을 수 있다면 NO를 출력,

또한 문자열을 insert 할 때 이미 저장된 문자열을 찾을 수 있었다면 NO를 출력하도록 코드를 작성했습니다.

다른 분들의 풀이와 비교하여 시간이 오래 걸린것으로 보아 비효율적인 탐색을 하고있는 것 같은데

트라이 개념에 익숙치 않아서 어느 부분을 수정하면 더 좋은 풀이가 가능할지 여쭤봅니다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int char_to_num(char c) {
	return c - '0';
}
struct Trie {
	Trie* children[10];
	bool isTerminal;

	Trie() :isTerminal(false) {
		memset(children, 0, sizeof(children));
	}

	~Trie() {
		for (int i = 0;i < 10;i++) {
			if (children[i])
				delete children[i];
		}
	}

	bool insert(const char* key) {
		if (isTerminal) return false;
		if (*key == 0) {
			isTerminal = true;
			return true;
		}
		int num = char_to_num(*key);
		if (children[num] == NULL)
			children[num] = new Trie();
		return children[num]->insert(key + 1);
	}
	Trie* find(const char* key) {
		if (*key == 0) return this;
		int num = char_to_num(*key);
		if (children[num] == NULL) {
			return NULL;
		}
		return children[num] -> find(key+1);
	}
};

void solve() {
	int n;
	scanf("%d", &n);
	Trie* root = new Trie();
	char s[11];
	bool ans = true;
	FOR(i, 0, n) {
		scanf("%s", s);
		ans = ans && (!root->find(s));
		ans = ans && (root->insert(s));
	}
	if (ans) printf("YES\n");
	else printf("NO\n");
}

int main() {
	int t = 1;
	scanf("%d", &t);
	while (t--) solve();
}

djm03178 2년 전 0

매번 new를 하여 노드를 생성하는 방식은 조금 느린 면이 있습니다. 미리 공간을 할당해두고 차례대로 부여해주는 것이 제 경험상 훨씬 빠릅니다.

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

문제

문제

출처

ICPC

제 풀이에 대해 질문드립니다.

sjlee0218 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말