•
사용 자료구조 : Trie
•
풀이 방법
마라톤에 참여한 선수들의 이름과, 완주에 성공한 사람들의 이름들이 주어집니다. 처음에 트라이에 마라톤에 참여한 선수들의 이름을 넣으려 했는데 이러면 완주에 성공하지 못한 선수의 이름을 찾기 위해 순회를 한번 더 해야한다는 생각이 들어서 완주에 성공한 사람들의 이름들을 통해 트라이를 구성하고 참여한 사람들의 이름을 하나씩 대입하여 찾는 방식으로 진행했습니다.
완벽히 코드를 작성했다고 생각했지만 계속 틀려서 시간이 좀 걸렸는데, 그 이유는 동명이인이 3명이 생길 수 있다는 사실을 간과했기 때문입니다. 따라서 trie를 구성할때 terminal을 bool 형이 아닌 int 형으로 두어서 동명이인을 카운트 하는 방식으로 진행했습니다.
•
코드
#include <iostream>
#include <vector>
int to_number(char ch)
{
return (ch - 'a');
}
struct Trie
{
std::vector<Trie *>children;
int terminal;
Trie(): terminal(false)
{
children.resize(26, nullptr);
}
~Trie()
{
for (size_t i = 0 ; i < 26 ; i++)
if (children[i])
delete children[i];
}
void insert(std::string &key, int i)
{
if (key[i] == '\0')
terminal++;
else
{
int next = to_number(key[i]);
if (children[next] == nullptr)
children[next] = new Trie();
children[next] -> insert(key, i+1);
}
}
Trie* find(std::string &key, int i)
{
if (key[i] == '\0')
{
if (!terminal)
return (nullptr);
terminal--;
return (this);
}
int next = to_number(key[i]);
if (children[next] == nullptr)
return (nullptr);
return (children[next]->find(key, i+1));
}
};
std::string solution(std::vector<std::string> participant, std::vector<std::string> completion)
{
Trie *p = new Trie();
std::string answer = "";
for (size_t i = 0 ; i < completion.size() ; i++)
p->insert(completion[i], 0);
for (size_t i = 0 ; i < participant.size(); i++)
if (!p->find(participant[i], 0) && participant.size() != 1)
{
answer = participant[i];
break;
}
delete p;
return (answer);
}
C++
복사
