• https://programmers.co.kr/learn/courses/30/lessons/42576

• 사용 자료구조 : 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);
}