글 읽기 - trie 사용해서 풀었습니다. (시간초과)

gogoshin85 7년 전 0

trie 사용해서 풀었는데요 시간 초과가 나는데

알고리즘을 바꿔야 하나요?

#include <iostream>

using namespace std;

class WORD
{
public:
	WORD() : bValid(false), nNum(-1), nLinkBuffer(9), nLinkSize(0)
	{
		link = new WORD*[nLinkBuffer];
	}

	~WORD()
	{

	}
	
	int		nLinkBuffer;
	int		nLinkSize;
	WORD**	link;
	bool	bValid;
	int		nNum;
	char	cChar;

	WORD* InsertWord(char cFind)
	{
		WORD* ret = FindWord(cFind);
		if (ret == NULL)
		{
			WORD* word = new WORD;
			word->cChar = cFind;

			link[nLinkSize] = word;
			ret = link[nLinkSize];
			nLinkSize++;

			if (nLinkSize >= nLinkBuffer) 
			{
				nLinkBuffer *= 2;
				WORD** newlink = new WORD*[nLinkBuffer];

				for (int i = 0; i < nLinkSize; i++)
				{
					newlink[i] = link[i];
				}

				delete[] link;
				link = newlink;
			}
		}
		return ret;
	}

	WORD* FindWord(char cFind)
	{
		for (int i = 0; i < nLinkSize; i++)
		{
			if (link[i]->cChar == cFind)
			{
				return link[i];
			}
		}
		return NULL;
	}

	void DeleteLink()
	{
		for (int i = 0; i < nLinkSize; i++)
		{
			link[i]->DeleteLink();
			delete link[i];
		}
	}
};

class TRIE
{
public:
	TRIE()
	{
		root = new WORD;
	}
	~TRIE()
	{
		DeleteTRIE();
	}
	WORD *root;

	int GetLength(char *words)
	{
		int i = 0;
		for (i = 0; i < 256; i++)
		{
			if (words[i] == '\0')
				return i;
		}
		return -1;
	}

	void InsertWord(char *words, int nNum)
	{
		int nWordSize = GetLength(words);

		WORD* temp = root;
		for (int i = 0; i < nWordSize; i++)
		{
			temp = temp->InsertWord(words[i]);
		}
		temp->bValid = true;
		temp->nNum = nNum;
	}

	int FindWord(char *words)
	{
		int nWordSize = GetLength(words);

		WORD* temp = root;
		for (int i = 0; i < nWordSize; i++)
		{
			if (temp == NULL)
			{
				return -1;
			}
			temp = temp->FindWord(words[i]);
		}
		if (temp->bValid == true)
		{
			return temp->nNum;
		}
		return -1;
	}

	void DeleteTRIE()
	{
		if (root != NULL)
		{
			root->DeleteLink();
			delete root;
			root = NULL;
		}
	}
};

int ToNumber(char *word) 
{
	int nRet = 0;
	
	int i = 0;
	int mul = 1;
	while (word[i] != '\0')
	{
		nRet *= 10;

		if (word[i] >= '0' && word[i] <= '9')
		{
			nRet += (word[i] - '1' + 1);
		}
		else 
		{
			return -1;
		}
		i++;
	}
	return nRet;
}

int main()
{
	//freopen("input.txt", "r", stdin);

	int nSize = 0;
	int nQSize = 0;
	cin >> nSize >> nQSize;

	TRIE trie;
	char **data = new char*[nSize + 1];

	for (int i = 1; i <= nSize; i++)
	{
		data[i] = new char[21];
	}
		
	for (int i = 1; i <= nSize; i++)
	{
		cin >> data[i];

		data[i][0] = data[i][0] - ('A' - 'a');
		trie.InsertWord(data[i], i);
	}

	char q1[21];
	for (int i = 0; i < nQSize; i++)
	{
		cin >> q1;
		int nQuest = ToNumber(q1);
		
		if (nQuest == -1)
		{
			q1[0] = q1[0] - ('A' - 'a');
			int nRes = trie.FindWord(q1);
			cout << nRes << endl;
		}
		else 
		{
			cout << data[nQuest] << endl;
		}
	}

	for (int i = 1; i <= nSize; i++)
	{
		delete [] data[i];
	}
	delete[] data;

	return 0;
}

tols91 7년 전 0

전 이거 cout로 시간초과나서 printf로 바꾸니까 AC받았던기억이..

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

문제

문제

출처

ICPC

trie 사용해서 풀었습니다. (시간초과)

gogoshin85 7년 전 0

tols91 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말