[C++] ํŠธ๋ผ์ด(Trie)

2020. 5. 8. 20:24ยท๐Ÿ“ Computer Science/โœ Algorithm

ํŠธ๋ผ์ด(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๋ฒˆ: ํœด๋Œ€ํฐ ์žํŒ

ํœด๋Œ€ํฐ์—์„œ ๊ธธ์ด๊ฐ€ P์ธ ์˜๋‹จ์–ด๋ฅผ ์ž…๋ ฅํ•˜๋ ค๋ฉด ๋ฒ„ํŠผ์„ P๋ฒˆ ๋ˆŒ๋Ÿฌ์•ผ ํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์‹œ์Šคํ…œํ”„๋กœ๊ทธ๋ž˜๋ฐ ์—ฐ๊ตฌ์‹ค์— ๊ทผ๋ฌดํ•˜๋Š” ์Šนํ˜์—ฐ๊ตฌ์›์€ ์‚ฌ์ „์„ ์‚ฌ์šฉํ•ด ์ด ์ž…๋ ฅ์„ ๋” ๋นจ๋ฆฌ ํ•  ์ˆ˜ ์žˆ๋Š” ์žํŒ ๋ชจ๋“ˆ์„ ๊ฐœ๋ฐœ

www.acmicpc.net

#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

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr

#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

๊ฐ๊ฐ์˜ Boggle์— ๋Œ€ํ•ด, ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ ์ˆ˜, ๊ฐ€์žฅ ๊ธด ๋‹จ์–ด, ์ฐพ์€ ๋‹จ์–ด์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•œ Boggle์—์„œ ๊ฐ™์€ ๋‹จ์–ด๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ์ฐพ์€ ๊ฒฝ์šฐ์—๋Š” ํ•œ ๋ฒˆ๋งŒ ์ฐพ์€ ๊ฒƒ์œผ๋กœ ์„ผ๋‹ค. ๊ฐ€์žฅ ๊ธด ๋‹จ์–ด๊ฐ€ ์—ฌ๋Ÿฌ ๊ฐœ

www.acmicpc.net

#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;
    }
};
์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)
'๐Ÿ“ Computer Science/โœ Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [C++] ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ(Segment Tree)
  • [C++] ๋น„ํŠธ๋งˆ์Šคํฌ(BitMask)
  • [C++] ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ(Union-Find)
  • [C++] ํˆฌ ํฌ์ธํ„ฐ(Two Pointer)
Blxxming
Blxxming
CS ์ง€์‹๊ณผ ๊ณต๋ถ€ํ•˜๋‹ค ๋ฐฐ์šด ๊ฒƒ, ๊ฒฝํ—˜ํ•œ ๊ฒƒ ๋“ฑ์„ ๊ธฐ๋กํ•˜๋Š” ๋ธ”๋กœ๊ทธ์ž…๋‹ˆ๋‹ค.
  • Blxxming
    ๐Ÿ’ก๋ฒˆ๋œฉ๐Ÿ’ก
    Blxxming
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
  • ๊ณต์ง€์‚ฌํ•ญ

    • Tech Interview
    • ๐Ÿ“š Tech (246)
      • ๐Ÿ“ Computer Science (96)
        • โœ OS (12)
        • โœ Network & Web (10)
        • โœ Database (11)
        • โœ Data Structure (6)
        • โœ Algorithm (40)
        • โœ Design Pattern (9)
        • โœ Cloud Computing (3)
        • โœ (5)
      • ๐Ÿ“ Language (73)
        • โœ Language (6)
        • โœ C & C++ (11)
        • โœ C# (19)
        • โœ JAVA (37)
      • ๐Ÿ“ Game (43)
        • โœ Computer Graphics (2)
        • โœ Unity (14)
        • โœ Unreal (26)
        • โœ (1)
      • ๐Ÿ“ Book (34)
        • โœ Effective (3)
        • โœ Game Server (16)
        • โœ Clean Code (14)
        • โœ (1)
  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.0
Blxxming
[C++] ํŠธ๋ผ์ด(Trie)
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”