[C++] 트라이(Trie)

트라이(Trie) 

여러 문자열을 효율적으로 저장하고 탐색하기 위한 트리 형태의 자료구조로 시간 복잡도는 O(n)이다.

 

기본 원리

 

{"AE" , "ATV", "ATES", "ATEV", "DE" ,"DC"}

 

struct Trie
{
	Trie* next[26];
	bool finish;

	Trie() :finish(false)
	{
		for (int i = 0; i < 26; ++i)
			next[i] = NULL;
	}

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

	void insert(const char* key)
	{
		if (*key == 0) {
			finish = true;
			return;
		}

		int curr = *key - 'a';
		if (next[curr] == NULL)
			next[curr] = new Trie();
		next[curr]->insert(key + 1);
	}

	bool find(const char* key)
	{
		if (*key == 0)
			return finish;

		int curr = *key - 'a';
		if (next[curr] != NULL)
			return next[curr]->find(key + 1);
		return false;
	}
};

 

문제

 

https://www.acmicpc.net/problem/5670

5670번: 휴대폰 자판

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

struct Trie
{
	Trie* next[26];
	bool finish;
	int cnt;

	Trie() :finish(false), cnt(0)
	{
		for (int i = 0; i < 26; ++i)
			next[i] = NULL;
	}

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

	void insert(const char* key)
	{
		if (*key == 0) {
			finish = true;
			return;
		}

		int curr = *key - 'a';
		if (next[curr] == NULL) {
			next[curr] = new Trie();
			cnt++;
		}
		next[curr]->insert(key + 1);
	}

	int find(const char* key, bool first = false)
	{
		if (*key == 0)
			return 0;

		int curr = *key - 'a';
		bool input = (first || finish || cnt > 1);
		return next[curr]->find(key + 1) + (input ? 1 : 0);
	}
};

int main()
{
	int n;
	while (cin >> n) {
		vector<string> str(n);
		Trie* trie = new Trie();
		for (int i = 0; i < n; ++i) {
			cin >> str[i];
			trie->insert(str[i].c_str());
		}

		int sum = 0;
		for (int i = 0; i < n; ++i)
			sum += trie->find(str[i].c_str(), true);
		printf("%.2f\n", (double)sum / n);

		delete trie;
	}
}

 

https://programmers.co.kr/learn/courses/30/lessons/60060

프로그래머스

#include <string>
#include <vector>
using namespace std;

int toNumber(char c)
{
	if (c == '?')
		return 26;
	return c - 'a';
}

struct Trie {
	Trie* next[27];
	int cnt;

	Trie() : cnt(0)
	{
		for (int i = 0; i < 27; ++i)
			next[i] = NULL;
	}

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

	void insert(const char* key)
	{
		if (*key == 0)
			return;

		int curr = toNumber(*key);
		if (next[curr] == NULL)
			next[curr] = new Trie();
		next[curr]->insert(key + 1);
	}

	void find(const char* key)
	{
		if (*key == 0) {
			cnt++;
			return;
		}

		int curr = toNumber(*key);
		if (next[curr] != NULL)
			next[curr]->find(key + 1);
		if (next[toNumber('?')] != NULL)
			next[toNumber('?')]->find(key + 1);
	}

	int getCnt(const char* key)
	{
		if (*key == 0)
			return cnt;

		int curr = toNumber(*key);
		if (next[curr] != NULL)
			return next[curr]->getCnt(key + 1);
	}
};

vector<int> solution(vector<string> words, vector<string> queries)
{
	vector<int> answer;
	Trie trie;

	for (int i = 0; i < queries.size(); ++i)
		trie.insert(queries[i].c_str());
	for (int i = 0; i < words.size(); ++i)
		trie.find(words[i].c_str());
	for (int i = 0; i < queries.size(); ++i)
		answer.push_back(trie.getCnt(queries[i].c_str()));

	return answer;
}

 

https://www.acmicpc.net/problem/9202

9202번: Boggle

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

struct Trie
{
	Trie* next[26];
	bool finish;

	Trie() :finish(false)
	{
		for (int i = 0; i < 26; ++i)
			next[i] = NULL;
	}

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

	void insert(const char* key)
	{
		if (*key == 0) {
			finish = true;
			return;
		}

		int curr = *key - 'A';
		if (next[curr] == NULL)
			next[curr] = new Trie();
		next[curr]->insert(key + 1);
	}

	int find(const char* key)
	{
		if (*key == 0)
			return finish ? 2 : 1;

		int curr = *key - 'A';
		if (next[curr] != NULL)
			return next[curr]->find(key + 1);
		return 0;
	}
};

Trie* trie;

const int SIZE = 4;
char board[SIZE][SIZE];
bool checked[SIZE][SIZE];
vector<string> findWords;
vector<int> points{ 0,0,0,1,1,2,3,5,11 };

void dfs(int x, int y, string word)
{
	if (0 > x || x >= SIZE || 0 > y || y >= SIZE || checked[y][x])
		return;

	word += board[y][x];
	int find = trie->find(word.c_str());
	if (find != 0) // 일치하는 글자 없음
	{
		if (find == 2)
			findWords.push_back(word);

		checked[y][x] = true;
		dfs(x + 1, y, word);
		dfs(x - 1, y, word);
		dfs(x, y + 1, word);
		dfs(x, y - 1, word);
		dfs(x + 1, y + 1, word);
		dfs(x + 1, y - 1, word);
		dfs(x - 1, y + 1, word);
		dfs(x - 1, y - 1, word);
		checked[y][x] = false;
	}
}

int main()
{
	trie = new Trie();
	int w, b;
	string s;

	scanf("%d", &w);
	getline(cin, s);

	for (int i = 0; i < w; ++i) {
		getline(cin, s);
		trie->insert(s.c_str());
	}
	getline(cin, s);

	scanf("%d", &b);
	while (b--) {
		getline(cin, s);
		for (int i = 0; i < 4; ++i) {
			getline(cin, s);
			for (int j = 0; j < 4; ++j)
				board[i][j] = s[j];
		}

		findWords.clear();
		for (int i = 0; i < SIZE; ++i)
			for (int j = 0; j < SIZE; ++j) {
				for (int k = 0; k < SIZE; ++k)
					for (int l = 0; l < SIZE; ++l)
						checked[k][l] = false;
				dfs(i, j, "");
			}

		sort(findWords.begin(), findWords.end(), [](string& a, string& b) {
			if (a.size() == b.size())
				return a < b;
			return a.size() > b.size();
			});
		findWords.erase(unique(findWords.begin(), findWords.end()), findWords.end());

		int score = 0, maxWord;
		for (int i = 0; i < findWords.size(); ++i)
			score += points[findWords[i].size()];

		cout << score << " " << (findWords.empty() ? "" : findWords[0]) << " " << findWords.size() << endl;
	}

	delete trie;
}

 

https://leetcode.com/problems/word-search-ii/

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

class Trie
{
public:
	Trie* next[26] { NULL };
	bool finish = false;

	void insert(string word)
	{
		if (word == "") {
			finish = true;
			return;
		}

		int curr = word[0] - 'a';
		if (next[curr] == NULL)
			next[curr] = new Trie();
		next[curr]->insert(word.erase(0, 1));
	}

	bool search(string word)
	{
		if (word == "")
			return finish;

		int curr = word[0] - 'a';
		if (next[curr] != NULL)
			return next[curr]->search(word.erase(0, 1));
		return false;
	}

	~Trie()
	{
		for (auto next : next)
			if (next != nullptr)
				delete(next);
	}
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie* trie = new Trie();
        for (int i = 0; i < words.size(); ++i)
            trie->insert(words[i]);

        vector<string> answer;
        for (int i = 0; i < board.size(); ++i)
            for (int j = 0; j < board[0].size(); ++j)
                dfs(board, i, j, trie, "", answer);

		delete(trie);
        return answer;
    }
    
    void dfs(vector<vector<char>>& board, int i, int j, Trie* trie, string word, vector<string>& answer) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size())
            return;
        if (board[i][j] == '0')
            return;

        trie = trie->next[board[i][j] - 'a'];
        if (trie == NULL)
            return;
        
        word += board[i][j];        
        if (trie->finish && IsContain(word, answer) == false)
            answer.push_back(word);

        char temp = board[i][j];
        board[i][j] = '0'; 
        
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        for (int x = 0; x < 4; x++)
                dfs(board, i + dx[x], j + dy[x], trie, word, answer);
        
        board[i][j] = temp; 
    }

    bool IsContain(string word, vector<string>& answer)
    {
        for (int i = 0; i < answer.size(); ++i)
            if (answer[i] == word)
                return true;
        return false;
    }
};