추라이 추라이
일단 Trie라는 단어를 처음 본 것 같다. 아마 Elastic Search에서 내부적으로 구현해 주고 있었겠지..?
- Trie?
- 검색 트리의 일종
- 노드가 특정 문자를 나타내며, 루트부터 특정 노드까지 이어지는 경로는 문자열을 나타내는 데이터 구조
- 문자열을 저장하고 검색하는 데 사용
- 접두사 특성(Prefix Property): 트라이의 각 노드는 해당 노드를 루트로 하는 서브 트리에 저장된 문자열들의 공통 접두사를 나타냄
- 노드의 자식들: 각 노드는 해당 노드를 기준으로 가능한 모든 다음 문자로 이어지는 자식 노드들을 가짐
- 마지막 노드 표시: 각 문자열의 끝을 표시하는 마지막 노드는 종종 특별한 마크나 플래그를 가짐
- 검색: 입력된 문자열의 길이 중 가장 긴 것의 길이에 따라, O(N)의 시간복잡도(한 문자마다 자식 노드로 내려가며 O(1)로 처리된다고 가정)
- 저장: 저장하려는 문자열의 길이에 따라, O(M)의 시간복잡도
- C++에서는 입력문자열 범위가 제한되지 않은 경우 unordered_map, 입력문자열 범위가 제한된 경우 배열을 사용하여 작성할 수 있다.
- 메모리 초과 코드 1: unordered_map 사용
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* current = root;
for (char ch : word) {
if (current->children.find(ch) == current->children.end()) {
current->children[ch] = new TrieNode();
}
current = current->children[ch];
}
current->isEndOfWord = true;
}
bool search(const string& word) {
TrieNode* current = root;
for (char ch : word) {
if (current->children.find(ch) == current->children.end()) {
return false;
}
current = current->children[ch];
}
return current->isEndOfWord;
}
};
string searchInTwoTries(Trie& trie1, Trie& trie2, const string& word) {
for (int i = 1; i <= word.length(); ++i) {
string prefix = word.substr(0, i);
string suffix = word.substr(i);
if (trie1.search(prefix) && trie2.search(suffix)) {
return "Yes";
}
}
return "No";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Trie trieColor;
Trie trieName;
int C, N, Q;
string color, name;
cin >> C;
cin >> N;
for (int i = 0; i < C; i++)
{
cin >> color;
trieColor.insert(color);
}
for (int i = 0; i < N; i++)
{
cin >> name;
trieName.insert(name);
}
cin >> Q;
string question[Q];
for (int i = 0; i < Q; i++)
{
cin >> question[i];
}
for (int i = 0; i < Q; i++)
{
cout << searchInTwoTries(trieColor, trieName, question[i]) << "\n";
}
return 0;
}
사용되는 문자열이 영문 소문자 알파벳만 있다고 했으니 26글자 제한을 두면 나아질까?
- 메모리 초과 코드 2: array 사용
#include <iostream>
using namespace std;
const int ALPHABET_SIZE = 26;
class TrieNode {
public:
TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {
for (int i = 0; i < ALPHABET_SIZE; ++i) {
children[i] = nullptr;
}
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* current = root;
for (char ch : word) {
int index = ch - 'a';
if (!current->children[index]) {
current->children[index] = new TrieNode();
}
current = current->children[index];
}
current->isEndOfWord = true;
}
bool search(const string& word) {
TrieNode* current = root;
for (char ch : word) {
int index = ch - 'a';
if (!current->children[index]) {
return false;
}
current = current->children[index];
}
return current->isEndOfWord;
}
};
string searchInTwoTries(Trie& trie1, Trie& trie2, const string& word) {
for (int i = 1; i <= word.length(); ++i) {
string prefix = word.substr(0, i);
string suffix = word.substr(i);
if (trie1.search(prefix) && trie2.search(suffix)) {
return "Yes";
}
}
return "No";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Trie trieColor;
Trie trieName;
int C, N, Q;
string color, name;
cin >> C;
cin >> N;
for (int i = 0; i < C; i++)
{
cin >> color;
trieColor.insert(color);
}
for (int i = 0; i < N; i++)
{
cin >> name;
trieName.insert(name);
}
cin >> Q;
string question[Q];
for (int i = 0; i < Q; i++)
{
cin >> question[i];
}
for (int i = 0; i < Q; i++)
{
cout << searchInTwoTries(trieColor, trieName, question[i]) << "\n";
}
return 0;
}deconstructor 추가
- 메모리 초과 코드 3:
#include <iostream>
#include <vector>
using namespace std;
const int ALPHABET_SIZE = 26;
class TrieNode {
public:
TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {
fill(children, children + ALPHABET_SIZE, nullptr);
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() : root(new TrieNode()) {}
void insert(const string& word) {
TrieNode* current = root;
for (char ch : word) {
int index = ch - 'a';
if (!current->children[index]) {
current->children[index] = new TrieNode();
}
current = current->children[index];
}
current->isEndOfWord = true;
}
bool search(const string& word) {
TrieNode* current = root;
for (char ch : word) {
int index = ch - 'a';
if (!current->children[index]) {
return false;
}
current = current->children[index];
}
return current->isEndOfWord;
}
~Trie() {
deleteTrie(root);
}
private:
void deleteTrie(TrieNode* node) {
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (node->children[i]) {
deleteTrie(node->children[i]);
}
}
delete node;
}
};
vector<string> searchInTwoTries(Trie& trie1, Trie& trie2, const string& word) {
vector<string> results;
for (int i = 1; i <= word.length(); ++i) {
string prefix = word.substr(0, i);
string suffix = word.substr(i);
if (trie1.search(prefix) && trie2.search(suffix)) {
results.push_back("Yes");
} else {
results.push_back("No");
}
}
return results;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Trie trieColor;
Trie trieName;
int C, N, Q;
string color, name;
cin >> C >> N;
for (int i = 0; i < C; i++) {
cin >> color;
trieColor.insert(color);
}
for (int i = 0; i < N; i++) {
cin >> name;
trieName.insert(name);
}
cin >> Q;
string question;
for (int i = 0; i < Q; i++) {
cin >> question;
vector<string> results = searchInTwoTries(trieColor, trieName, question);
for (const string& result : results) {
cout << result << "\n";
}
}
return 0;
}
나 사실 첫 번째 코드 만들고 되게 기뻤는데.. 예상대로 출력이 나오는 건 쉽지만 메모리 초과를 잡기 힘든 문제였다..
메모리 초과가 안 나는 남의 코드를 보면..
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 2001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
using namespace std;
struct TRIE {
bool isEnd;
vector<pair<char, TRIE*> > Child;
TRIE() {
isEnd = false;
Child.clear();
}
void insert_Pattern(string Pattern) {
TRIE* NowTrie = this;
for (int i = 0; i < Pattern.size(); i++) {
char Now = Pattern[i];
bool Flag = false;
for (auto A : NowTrie->Child) {
if (A.first == Now) {
Flag = true;
NowTrie = A.second;
break;
}
}
if (!Flag) {
NowTrie->Child.push_back(make_pair(Now, new TRIE));
NowTrie = NowTrie->Child.back().second;
}
}
NowTrie->isEnd = true;
}
};
int C, N, Q;
string S;
bool Color[MAX], Nickname[MAX];
void init() {
for (int i = 0; i < MAX; i++) {
Color[i] = false;
Nickname[i] = false;
}
}
bool query(TRIE* Root1, TRIE* Root2) {
TRIE* ColorTrie = Root1;
TRIE* NicknameTrie = Root2;
for (int i = 0; i < S.size(); i++) {
char Now = S[i];
bool Flag = false;
for (auto A : ColorTrie->Child) {
if (A.first == Now) {
Flag = true;
ColorTrie = A.second;
break;
}
}
if (!Flag) {
break;
}
if (ColorTrie->isEnd) {
Color[i] = true;
}
}
for (int i = ((int)S.size() - 1); i >= 0; i--) {
char Now = S[i];
bool Flag = false;
for (auto A : NicknameTrie->Child) {
if (A.first == Now) {
Flag = true;
NicknameTrie = A.second;
break;
}
}
if (!Flag) {
break;
}
if (NicknameTrie->isEnd) {
Nickname[i] = true;
}
}
for (int i = 0; i < ((int)S.size()); i++) {
if (Color[i] && Nickname[i + 1]) {
return true;
}
}
return false;
}
void input() {
TRIE* ColorTrie = new TRIE();
TRIE* NicknameTrie = new TRIE();
cin >> C >> N;
for (int i = 0; i < C; i++) {
cin >> S;
ColorTrie->insert_Pattern(S);
}
for (int i = 0; i < N; i++) {
cin >> S;
reverse(S.begin(), S.end());
NicknameTrie->insert_Pattern(S);
}
cin >> Q;
while (Q--) {
init();
cin >> S;
bool Answer = query(ColorTrie, NicknameTrie);
if (Answer) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
};
delete ColorTrie;
delete NicknameTrie;
}
int main() {
FASTIO
input();
return 0;
}color와 nickname의 True/False를 체크하는 배열을 만들었고, 닉네임을 거꾸로 해서 insert했다.
다른 풀이도 찾아 보면 Trie의 자식노드를 unordered_map으로 만든 것은 문제가 아니고, memset과 constructor와 deconstructor를 사용해서 메모리를 관리해준 것, 검색 결과 bool 배열을 만든 것이 차이로 보인다. string 대신 char*를 사용하는 경우도 있었다.
재미는 있었는데 이해가 전혀 안 됐기 때문에
이해가 안 됐는데 왜 재미가 있어요.. 이상한 사람이다..
앞으로는 과욕을 좀 버리고 토끼같은 기초 알고리즘 책을 공부할 예정
