알고스팟: 안녕히, 그리고 물고기는 고마웠어요! (ID: SOLONG)

[문제 링크]

algospot.com :: SOLONG

---

이 문제와 같이 많은 양의 문자열을 검색하는 요구하는 문제들은 트라이 자료구조를 활용하면 효율적으로 해결할 수 있다.

 

트라이 자료구조는 알고리즘 문제해결 전략에서 구현한 것과 똑같이 구현하였다.

 

사전에 포함된 단어들을 출현 빈도에 따라 내림차순으로 정렬하고 출현 빈도가 같을 경우 오름차순으로 정렬하기 위해 출현 빈도 freq에 -를 붙여서 배열에 담았다.

 

스페이스바를 누르는 횟수까지 포함시켜야 하므로 cnt를 M - 1 로 초기화 하였다.

---

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

const int ALPHABETS = 26;

int toNumber(char ch) 
{ 
	return ch - 'A'; 
}

struct TrieNode
{
	TrieNode* children[ALPHABETS];
	int first;
	int terminal;

	TrieNode() : terminal(-1), first(-1)
	{
		memset(children, 0, sizeof(children));
	}
	~TrieNode()
	{
		for (int i = 0; i < ALPHABETS; i++)
			if (children[i]) delete children[i];
	}

	void insert(string& key, int here, int id)
	{
		if (first == -1) 
			first = id;

		if (here == key.size())
			terminal = id;
		else
		{
			int next = toNumber(key[here]);

			//자식 노드가 없다면 생성
			if (children[next] == NULL)
				children[next] = new TrieNode();

			children[next]->insert(key, here + 1, id);
		}
	}

	int type(string& key, int here, int id)
	{
		if (here == key.size()) return 0;

		if (first == id) return 1;

		int next = toNumber(key[here]);

		return 1 + children[next]->type(key, here + 1, id);
	}

	TrieNode* find(string& key, int here)
	{
		if (here == key.size()) return this;
		
		int next = toNumber(key[here]);

		if (children[next] == NULL) return NULL;
		return children[next]->find(key, here + 1);
	}
};

int countKeys(TrieNode& trie, string word)
{
	TrieNode* node = trie.find(word, 0);

	if (node == NULL || node->terminal == -1)
		return word.size();

	return trie.type(word, 0, node->terminal);
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N, M;
		cin >> N >> M;

		
		vector<pair<int, string>> input;

		for (int i = 0; i < N; i++)
		{
			string words;
			int freq;
			cin >> words >> freq;
			input.push_back({ -freq, words });
		}

		sort(input.begin(), input.end());

		TrieNode word;
		
		for(int i=0; i<input.size(); i++)
			word.insert(input[i].second, 0, i);
		
		word.first = -1;

		int cnt = M - 1;

		for (int i = 0; i < M; i++)
		{
			string words;
			cin >> words;

			cnt += countKeys(word, words);
		}

		cout << cnt << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 144 day