글 읽기 - 시간초과가 어디서 날까요?

raararaara 5년 전 0

c 스럽게 짜봤는데 어느부분이 시간초과를 유발하는지 모르겠습니다.

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

typedef struct node* nptr;
typedef struct node {
	char data;
	bool valid;
	nptr child[26];
}NODE;

int n, m;
nptr head;

nptr makenode(char data, int idx, int Size, nptr prev) {
	if (!prev->child[data - 'a']) {
		nptr tmp = (nptr)malloc(sizeof(NODE));
		tmp->data = data;
		if (idx + 1 == Size) tmp->valid = true;
		else tmp->valid = false;
		for (int i = 0; i < 26; i++)
			tmp->child[i] = NULL;

		prev->child[data - 'a'] = tmp;
		return tmp;
	}
	else return prev->child[data - 'a'];
}

void init() {
	cin >> n >> m;
	head = (nptr)malloc(sizeof(NODE));
	for (int i = 0; i < 26; i++)
		head->child[i] = NULL;
}

bool find(string str, int idx, nptr prev) {
	if (str.size() == idx) {
		if (prev->valid == true)
			return true;
		else return false;
	}
	bool ans = false;

	if (prev->child[str[idx] - 'a'])
		ans = find(str, idx + 1, prev->child[str[idx] - 'a']);

	return ans;
}

int main() {
	init();

	for (int i = 0; i < n; i++) {
		nptr prev = head;
		string str[10000];
		cin >> str[i];

		int Size = str[i].size();
		for (int j = 0; j < Size; j++) {
			prev = makenode(str[i][j], j, Size, prev);
		}
	}

	int ans = 0;
	for (int i = 0; i < m; i++) {
		string str;
		cin >> str;

		int Size = str.size();
		if (find(str, 0, head)) ans++;
	}
	cout << ans << endl;
	for (int i = 0; i < n; i++) {

	}
	return 0;
}

sgchoi5 5년 전 1

입력 조건을 보면 최대 500 자를 가지는 문자열 만 개가 있고, 만 번을 쿼리를 하니 그냥 비교하면 시간 초과가 나오게 될 듯 하고요.

저는 간단한 hash 함수 이용해서 풀어봤습니다. hash table 만들어두면 검색시에는 비교 없이 O(1) 로 존재여부를 알 수 있으니..

raararaara 5년 전 0

답변 감사합니다. 답변해주신 방향으로 고민해보겠습니다!

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

문제

문제

출처

ICPC

시간초과가 어디서 날까요?

raararaara 5년 전 0

sgchoi5 5년 전 1

raararaara 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말