[백준][C++] 7432: 디스크 트리

문제

7432번: 디스크 트리

풀이

문자열, 트라이

 

[백준][C++] 14725: 개미굴

위의 문제와 같은 풀이로, vector에 넣을 string을 '\'로 나눠서 넣는다. 

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

struct Trie
{
	map<string, Trie*> child;

	~Trie()
	{
		for (pair<string, Trie*> c : child)
		{
			delete c.second;
		}
	}

	void InsertWord(vector<string>& wordList, int idx)
	{
		if (wordList.size() == idx)
		{
			return;
		}

		// 현재 Trie의 child 중에서 wordList[idx]가 없다면 Trie를 새로 만들어서 child에 넣는다.
		if (child.find(wordList[idx]) == child.end())
		{
			Trie* trie = new Trie();

			child.insert(make_pair(wordList[idx], trie));
		}

		// wordList[idx]를 넣은 child로 가서 wordList[idx + 1]를 넣는다.
		child[wordList[idx]]->InsertWord(wordList, idx + 1);
	}

	void Print(int depth)
	{
		for (pair<string, Trie*> c : child)
		{
			for (int i = 0; i < depth; ++i)
			{
				cout << " ";
			}
			cout << c.first << '\n';

			c.second->Print(depth + 1);
		}
	}
};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	Trie trie;

	while (N--)
	{
		string s;
		cin >> s;

		string temp;
		vector<string> wordList;

		for (char c : s)
		{
			if (c == '\\')
			{
				wordList.push_back(temp);
				temp.clear();
			}
			else
			{
				temp.push_back(c);
			}
		}
		wordList.push_back(temp);

		trie.InsertWord(wordList, 0);
	}

	trie.Print(0);

	return 0;
}