int Cnt;

struct Trie

{

Trie()

{

isEnd = false;

}


~Trie()

{

for (auto it = child.begin(); it != child.end();)

{

if (it->second)

child.erase(it++);

else

++it;

}

}


void insertOne(string& str)

{

Trie* now = this;

for (int i = 0; i < str.length(); i++)

{

if (now->child.find(str[i]) == now->child.end())

{

now->child[str[i]] = new Trie();


if (i == str.length() - 1)

now->child[str[i]]->isEnd = true;

}

now = now->child[str[i]];

}

}


bool find(string& key)

{

Trie* now = this;

for (int i = 0; i < key.length(); i++)

{

if (now->child.find(key[i]) == now->child.end())

return false;


now = now->child[key[i]];

}

if (now->isEnd == true)

return true;

return false;

}


map<char, Trie*> child;

bool isEnd;

};


int main()

{

#define init cin.tie(0)->ios_base::sync_with_stdio(0);


cin >> N >> M;

vector<string> strings;

for (int i = 0; i < N; i++)

{

string temp;

cin >> temp;

strings.push_back(temp);

}


vector<string> mission;

for (int i = 0; i < M; i++)

{

string temp;

cin >> temp;

mission.push_back(temp);

}


Trie* Root = new Trie();

for (auto& string : strings)

{

Root->insertOne(string);

}

for (auto& string : mission)

{

if (Root->find(string) == true)

Cnt++;

}


cout << Cnt << '\n';

}


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

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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


분명 반례 다 넣어봐도 맞게 나오고

널리 퍼진 답안과 다른 점은 트라이 알고리즘을 짤때 재귀로 하지 않고 반복으로 했다는점인데

혹시 제가 구현할 때 놓친게 있을까요? 91퍼에서 자꾸 틀렸다고 나와서 계속 돌려보는데도 안보이네요


또 궁금한 점은 자식노드를 저장할 때 map을 사용했는데

포인터 배열을 사용하는거랑 map을 사용하는거랑 어느쪽이던 큰 차이가 없는건가요? 아무래도 포인터 배열로 index 기반으로 하면

빈 공간이 많이 생길거같아서 map이 효율적일거같아 map을 썼는데 이부분도 맞는지 궁금해요


정리하자면

1. 위의 코드 (트라이 구현)에서 틀린 점이 어디인지 궁금합니다.

2. 트라이 구현할 때 포인터 배열 대신 map, 재귀함수 대신 for문으로 구현해도 괜찮은지 궁금합니다.