[백준/BOJ] 백준 20541번 : 앨범정리

www.acmicpc.net/problem/20541

20541번: 앨범정리

앨범 정보를 구조체(node)에 저장하고, 앨범 구조를 트리 구조로 만들어 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <set>
#include <map>
using namespace std;

int n;
struct node {

	node* parent; //부모 노드
	string name; //현재 앨범 이름
	set<string> photo; //해당 앨범이 가지고 있는 사진
	map<string, node*> children; //(앨범 이름, 자식노드)
};
map<string, node*>::iterator it;
set<string>::iterator s_it;

node* Make_node()
{
	node* ret = new node();

	ret->parent = NULL;

	return ret;
}

pair<int, int> Delete(node* here)
{
	int album_cnt = 0;
	int photo_cnt = 0;

	album_cnt += 1; //해당 앨범
	photo_cnt += here->photo.size(); //해당 앨범의 사진 개수

	for (map<string, node*>::iterator temp_it = here->children.begin(); temp_it != here->children.end(); temp_it++)
	{
		pair<int, int> there_ret = Delete((*temp_it).second);

		album_cnt += there_ret.first;
		photo_cnt += there_ret.second;
	}

	//(사라지는 앨범의 개수, 사라지는 사진의 개수)
	return make_pair(album_cnt, photo_cnt);
}

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

	cin >> n;
	cin.ignore();

	node* root = Make_node();
	root->name = "album";

	node* here = root;
	for (int i = 0; i < n; i++)
	{
		string input;
		string command;
		string s;
		int index;

		getline(cin, input);

		index = input.find(" ");

		command = input.substr(0, index);
		s = input.substr(index + 1);

		if (command == "mkalb")
		{
			if (here->children.count(s) != 0)
			{
				cout << "duplicated album name" << "\n";
			}

			else
			{
				node* maked = Make_node();
				maked->parent = here;
				maked->name = s;

				here->children.insert(make_pair(s, maked));
			}
		}

		else if (command == "rmalb")
		{
			pair<int, int> delete_ret;
			if (s == "-1")
			{
				//속해있는 앨범이 존재 할때
				if (here->children.size() != 0)
				{
					it = here->children.begin();
					delete_ret = Delete((*it).second);
					cout << delete_ret.first << " " << delete_ret.second << "\n";

					here->children.erase(it);
				}

				else
					cout << 0 << " " << 0 << "\n";
			}

			else if (s == "0")
			{
				if (here->children.size() != 0)
				{
					int album_cnt = 0;
					int photo_cnt = 0;

					for (it = here->children.begin(); it != here->children.end(); it++)
					{
						delete_ret = Delete((*it).second);
						album_cnt += delete_ret.first;
						photo_cnt += delete_ret.second;
					}

					cout << album_cnt << " " << photo_cnt << "\n";
					here->children.clear();
				}

				else
					cout << 0 << " " << 0 << "\n";
			}

			else if (s == "1")
			{
				//속해있는 앨범이 존재 할때
				if (here->children.size() != 0)
				{
					it = here->children.end();
					it--;

					delete_ret = Delete((*it).second);
					cout << delete_ret.first << " " << delete_ret.second << "\n";

					here->children.erase(it);
				}

				else
					cout << 0 << " " << 0 << "\n";
			}

			else
			{
				if (here->children.count(s) != 0)
				{
					it = here->children.find(s);

					delete_ret = Delete((*it).second);
					cout << delete_ret.first << " " << delete_ret.second << "\n";

					here->children.erase(it);
				}

				else
					cout << 0 << " " << 0 << "\n";
			}
		}

		else if (command == "insert")
		{
			//해당 사진이 존재하지 않을때
			if (here->photo.count(s) == 0)
			{
				here->photo.insert(s);
			}

			else
				cout << "duplicated photo name" << "\n";
		}

		else if (command == "delete")
		{
			if (s == "-1")
			{
				if (here->photo.size() != 0)
				{
					s_it = here->photo.begin();

					here->photo.erase(s_it);

					cout << 1 << "\n";
				}

				else
					cout << 0 << "\n";
			}

			else if (s == "0")
			{
				cout << here->photo.size() << "\n";

				here->photo.clear();

			}

			else if (s == "1")
			{
				if (here->photo.size() != 0)
				{
					s_it = here->photo.end();
					s_it--;

					here->photo.erase(s_it);

					cout << 1 << "\n";
				}

				else
					cout << 0 << "\n";
			}

			else
			{
				if (here->photo.count(s) != 0)
				{
					s_it = here->photo.find(s);
					here->photo.erase(s_it);

					cout << 1 << "\n";
				}

				else
					cout << 0 << "\n";
			}
		}

		else if (command == "ca")
		{
			if (s == "..")
			{
				if (here->name != "album")
				{
					here = here->parent;
				}
			}

			else if (s == "/")
			{
				here = root;
			}

			else
			{
				if (here->children.count(s) != 0)
				{
					it = here->children.find(s);

					here = (*it).second;
				}
			}

			cout << here->name << "\n";

		}
	}


	return 0;
}