[BOJ/Platinum 5] 백준 20541 앨범정리(C++)

문제 링크

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

20541번: 앨범정리

지혜는 컴퓨터에 있는 사진들을 정리하기 위해 앨범정리 프로그램을 만들었다. 지혜가 만든 앨범정리 프로그램은 기본적으로 "album" 앨범이 존재하며 "album" 앨범은 절대로 삭제할 수 없다.

www.acmicpc.net

문제

지혜는 컴퓨터에 있는 사진들을 정리하기 위해 앨범정리 프로그램을 만들었다. 지혜가 만든 앨범정리 프로그램은 기본적으로 "album" 앨범이 존재하며 "album" 앨범은 절대로 삭제할 수 없다. 프로그램을 실행시키면 "album" 앨범부터 시작하여 명령어들을 통해 앨범 삭제/추가, 사진 삭제/추가, 현재앨범 이동 등을 할 수 있다. 앨범정리 프로그램은 다음과 같은 명령어 들로 구성 되어 있다. 수행할 명령어의 개수 N이 주어질 때 각 명령어 수행 후 문자열 출력이 필요한 명령어에 대해서 문자열을 출력한다.

mkalb
- 명령어 수행후: 현재 앨범에 속해있는 앨범 중 동일한 이름을 가진 앨범이 존재하여 앨범이 생성되지 않았으면 "duplicated album name"을 출력합니다. 그렇지 않다면 아무것도 출력하지 않습니다.
- mkalb S
  - 현재 앨범에 S 의 이름을 가진 앨범을 생성합니다.
  - 현재 앨범에 속해있는 앨범 중 동일한 이름을 가진 앨범이 존재하면 앨범을 생성하지 않습니다.
rmalb
- 명령어 수행후: 삭제된 앨범의 개수와 사진의 개수를 공백으로 구분하여 출력합니다.
- rmalb S
  - 현재 앨범에 속해있는 앨범 중 S 의 이름을 가진 앨범이 존재한다면, 해당 앨범을 삭제합니다.
  - 삭제된 앨범에 속한 모든 앨범과 사진들 또한 삭제됩니다.
- rmalb -1
  - 현재 앨범에 속해있는 앨범이 존재한다면, 이름이 사전순으로 가장 빠른 앨범을 삭제 합니다.
  - 삭제된 앨범에 속한 모든 앨범과 사진들 또한 삭제됩니다.
- rmalb 0
  - 현재 앨범에 속해있는 모든 앨범을 삭제 합니다.
  - 삭제된 앨범에 속한 모든 앨범과 사진들 또한 삭제됩니다.
- rmalb 1
  - 현재 앨범에 속해있는 앨범이 존재한다면, 이름이 사전순으로 가장 늦은 앨범을 삭제 합니다.
  - 삭제된 앨범에 속한 모든 앨범과 사진들 또한 삭제됩니다.
insert
- 명령어 수행후: 현재 앨범에 속해있는 사진 중에 동일한 이름을 가진 사진이 존재하여 사진이 삽입되지 않았으면 "duplicated photo name"을 출력합니다. 그렇지 않다면 아무것도 출력하지 않습니다.
- insert S
  - 현재 앨범에 S 의 이름을 가진 사진을 삽입합니다.
  - 현재 앨범에 속해있는 사진 중 동일한 이름을 가진 사진이 존재하면 사진을 삽입하지 않습니다.
delete
- 명령어 수행후: 삭제된 사진의 개수를 출력합니다.
- delete S
  - 현재 앨범에 속해있는 사진 중 S 의 이름을 가진 사진이 존재한다면, 해당 사진을 삭제합니다.
- delete -1
  - 현재 앨범에 속해있는 사진이 존재한다면, 이름이 사전순으로 가장 빠른 사진을 삭제 합니다.
- delete 0
  - 현재 앨범에 속해있는 모든 사진을 삭제합니다.
- delete 1
  - 현재 앨범에 속해있는 사진이 존재한다면, 이름이 사전순으로 가장 늦은 사진을 삭제 합니다.
ca
- 명령어 수행후: 현재 앨범 이름을 출력합니다.
- ca S
  - 현재 앨범에 속해있는 앨범 중 S 의 이름을 가진 앨범으로 이동합니다.
  - 현재 앨범에 속해있는 앨범 중 S 의 이름을 가진 앨범이 없다면 현재 앨범에 머무릅니다.
- ca ..
  - 현재 앨범의 상위 앨범으로 이동합니다.
  - 현재 앨범이 최상위 앨범인 "album" 앨범이라면 현재 앨범에 머무릅니다.
- ca /
  - 최상위 앨범인 "album" 앨범으로 이동합니다.

"A가 B에 속해있다"라는 것은 A의 바로 하위에 B가 있다는 것을 의미합니다. 만약 A가 B에 속해있고, B가 C에 속해있는 경우, A는 C에 속해 있는 것이 아닙니다.

입력

첫째 줄에 수행할 명령어의 개수 N이 주어진다.

다음줄 부터 N줄에 걸쳐 앨범정리 프로그램의 명령어가 주어진다.

출력

문제 본문에 나와있는 앨범정리 프로그램 명령어의 설명에 따라 적절한 문자열을 출력한다.

제한

1 ≤ N ≤ 105
1 ≤ S의 길이 ≤ 20
S는 공백을 포함하지 않은 알파벳 소문자로만 이루어져 있다.

예제 입력 1

24
mkalb animal
mkalb insect
ca animal
mkalb sky
mkalb land
mkalb ocean
ca land
insert elephant
insert tiger
insert banana
delete banana
ca elephant
ca ..
ca ocean
insert whale
ca /
ca insect
mkalb land
mkalb sky
ca ocean
ca ..
ca ..
rmalb -1
rmalb -1

예제 출력 1

animal
land
1
land
animal
ocean
album
insect
insect
album
album
4 3
3 0

예제 입력 2

29
mkalb domestic
mkalb ovarseas
ca domestic
ca incheon
mkalb incheon
ca incheon
mkalb chinatown
mkalb wolmido
ca chinatown
insert jajangmyeon
insert champon
insert friedrice
insert jajangmyeon
ca /
ca domestic
rmalb incheon
ca /
rmalb ovarseas
mkalb overseas
ca overseas
mkalb japanese
mkalb europe
rmalb japanese
ca europe
rmalb 0
ca ..
delete europe
ca ..
rmalb 1

예제 출력 2

domestic
domestic
incheon
chinatown
duplicated photo name
album
domestic
3 3
album
1 0
overseas
1 0
europe
0 0
overseas
0
album
2 0

예제 입력 3

30
mkalb univ
mkalb middle
mkalb elementary
insert middle
ca middle
insert middleschool
ca ..
rmalb middle
ca univ
mkalb inha
insert kaist
insert harvard
delete harvard
ca inha
mkalb inkyungho
mkalb hightech
mkalb jungseok
delete 0
rmalb 1
ca jungseok
ca hightech
mkalb computer
mkalb elect
mkalb machine
rmalb 1
rmalb 1
insert computer
insert elect
ca /
rmalb 0

예제 출력 3

middle
album
1 1
univ
1
inha
0
1 0
inha
hightech
1 0
1 0
album
6 3

알고리즘 분류

구현
자료 구조

풀이

네이버 부캠 입성을 위해 구현 문제만 풀고 있었기 때문에 트리 알고리즘의 구현 방법을 잘 몰라서 찾아보면서 풀어보았다.

트리를 잘 관리할 수만 있다면 어렵지 않고 상당히 재미있는 문제였다. 비슷한 문제가 있나 더 찾아봐야겠다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100005
#define LL long long
#define INF 1e9

using namespace std;
struct NODE {
	NODE* Parent;
	string Name;
	set<string> Photo;
	map<string, NODE*> Child;
};

int N;
NODE* Root;
NODE* Cur_Album;
map<string, NODE*>::iterator MIT;
set<string>::iterator SIT;

NODE* Make_Node() {
	NODE* Node = new NODE();
	Node->Parent = NULL;
	return Node;
}

void init() {
	Root = Make_Node();
	Root->Name = "album";
	Cur_Album = Root;
}

pair<int, int> Delete_Album(NODE* Node) {
	int Album_Cnt = 1;
	int Photo_Cnt = Node->Photo.size();
	map<string, NODE*>::iterator IT;
	for (IT = Node->Child.begin(); IT != Node->Child.end(); IT++) {
		pair<int, int> Deleted_Album = Delete_Album((*IT).second);
		Album_Cnt += Deleted_Album.first;
		Photo_Cnt += Deleted_Album.second;
	}
	return make_pair(Album_Cnt, Photo_Cnt);
}

int main() {
	FIRST
	cin >> N;
	init();
	for (int i = 0; i < N; i++) {
		string CMD;
		cin >> CMD;
		if (CMD == "mkalb") {
			string S;
			cin >> S;
			if (Cur_Album->Child.find(S) != Cur_Album->Child.end()) {
				/*
					현재 앨범(Cur_Album)에서 map.find() 함수를 이용해서 만들고자 하는 앨범의 이름 S가 이미 있는지 찾는다.
					있으면 duplicated album name을 출력한다.
				*/
				cout << "duplicated album name" << "\n";
			}
			else {
				NODE* child = Make_Node();
				child->Parent = Cur_Album;
				child->Name = S;
				Cur_Album->Child.insert(make_pair(S, child));
			}
		}
		else if (CMD == "rmalb") {
			string S;
			cin >> S;
			pair<int, int> Deleted_Album;
			if (S == "-1") {
				// 현재 앨범(Cur_Album)에 속해있는 앨범이 존재한다면, 이름이 사전순으로 가장 빠른 앨범을 삭제한다.
				if (Cur_Album->Child.size() > 0) {
					MIT = Cur_Album->Child.begin();
					Deleted_Album = Delete_Album((*MIT).second);
					cout << Deleted_Album.first << " " << Deleted_Album.second << "\n";
					Cur_Album->Child.erase(MIT);
				}
				else {
					cout << 0 << " " << 0 << "\n";
				}
			}
			else if (S == "0") {
				// 현재 앨범(Cur_Album)에 속해있는 모든 앨범을 삭제한다.
				if (Cur_Album->Child.size() > 0) {
					int Album_Cnt = 0;
					int Photo_Cnt = 0;
					for (MIT = Cur_Album->Child.begin(); MIT != Cur_Album->Child.end(); MIT++) {
						Deleted_Album = Delete_Album((*MIT).second);
						Album_Cnt += Deleted_Album.first;
						Photo_Cnt += Deleted_Album.second;
					}
					cout << Album_Cnt << " " << Photo_Cnt << "\n";
					Cur_Album->Child.clear();
				}
				else {
					cout << 0 << " " << 0 << "\n";
				}
			}
			else if (S == "1") {
				// 현재 앨범(Cur_Album)에 속해있는 앨범이 존재한다면, 이름이 사전순으로 가장 늦은 앨범을 삭제한다.
				if (Cur_Album->Child.size() > 0) {
					MIT = Cur_Album->Child.end();
					MIT--;
					Deleted_Album = Delete_Album((*MIT).second);
					cout << Deleted_Album.first << " " << Deleted_Album.second << "\n";
					Cur_Album->Child.erase(MIT);
				}
				else {
					cout << 0 << " " << 0 << "\n";
				}
			}
			else {
				// 현재 앨범(Cur_Album)에 속해있는 앨범 중 S의 이름을 가진 앨범이 존재한다면 해당 앨범을 삭제한다.
				if (Cur_Album->Child.find(S) != Cur_Album->Child.end()) {
					MIT = Cur_Album->Child.find(S);
					Deleted_Album = Delete_Album((*MIT).second);
					cout << Deleted_Album.first << " " << Deleted_Album.second << "\n";
					Cur_Album->Child.erase(MIT);
				}
				else {
					cout << 0 << " " << 0 << "\n";
				}
			}
		}
		else if (CMD == "insert") {
			string S;
			cin >> S;
			if (Cur_Album->Photo.find(S) != Cur_Album->Photo.end()) {
				/*
					현재 앨범(Cur_Album)에서 set.find() 함수를 이용해서 만들고자 하는 사진의 이름 S가 이미 있는지 찾는다.
					있으면 duplicated photo name을 출력한다.
				*/
				cout << "duplicated photo name" << "\n";
			}
			else {
				Cur_Album->Photo.insert(S);
			}
		}
		else if (CMD == "delete") {
			int Deleted_Photo = 0;
			string S;
			cin >> S;
			if (S == "-1") {
				// 현재 앨범(Cur_Album)에 속해있는 사진이 존재한다면, 이름이 사전순으로 가장 빠른 사진을 삭제한다.
				if (Cur_Album->Photo.size() > 0) {
					SIT = Cur_Album->Photo.begin();
					Cur_Album->Photo.erase(SIT);
					Deleted_Photo++;
				}
			}
			else if (S == "0") {
				// 현재 앨범(Cur_Album)에 속해있는 모든 사진을 삭제한다.
				if (Cur_Album->Photo.size() > 0) {
					SIT = Cur_Album->Photo.begin();
					for (SIT = Cur_Album->Photo.begin(); SIT != Cur_Album->Photo.end(); SIT++) {
						Deleted_Photo++;
					}
					Cur_Album->Photo.clear();
				}
			}
			else if (S == "1") {
				// 현재 앨범(Cur_Album)에 속해있는 사진이 존재한다면, 이름이 사전순으로 가장 늦은 사진을 삭제한다.
				if (Cur_Album->Photo.size() > 0) {
					SIT = Cur_Album->Photo.end();
					SIT--;
					Cur_Album->Photo.erase(SIT);
					Deleted_Photo++;
				}
			}
			else {
				// 현재 앨범(Cur_Album)에 속해있는 사진 중 S의 이름을 가진 사진이 존재한다면 그 사진을 삭제한다.
				if (Cur_Album->Photo.find(S) != Cur_Album->Photo.end()) {
					SIT = Cur_Album->Photo.find(S);
					Cur_Album->Photo.erase(SIT);
					Deleted_Photo++;
				}
			}
			cout << Deleted_Photo << "\n";
		}
		else if (CMD == "ca") {
			string S;
			cin >> S;
			if (S == "..") {
				// 현재 앨범이 최상위 앨범인 album이라면 이동하지 않고, 그게 아니라면 상위 앨범으로 이동한다.
				if (Cur_Album->Name != "album") {
					Cur_Album = Cur_Album->Parent;
				}
			}
			else if (S == "/") {
				// 최상위 앨범인 album으로 이동한다.
				Cur_Album = Root;
			}
			else {
				// 현재 앨범에 속해있는 앨범 중 S의 이름을 가진 앨범으로 이동하며, S가 없다면 현재 앨범에 머무른다.
				if (Cur_Album->Child.find(S) != Cur_Album->Child.end()) {
					MIT = Cur_Album->Child.find(S);
					Cur_Album = (*MIT).second;
				}
			}
			cout << Cur_Album->Name << "\n";
		}
	}

	return 0;
}

'BOJ > Platinum ~ Diamond' 카테고리의 다른 글

[BOJ/Platinum 5] 백준 14632 고급 작품(C++) (0)	2022.02.04
[BOJ/Platinum 4] 백준 15778 Yut Nori(C++) (0)	2022.02.04
[BOJ/Platinum 5] 백준 17377 Taxi(C++) (0)	2022.02.01
[BOJ/Platinum 5] 백준 18891 제21대 국회의원 선거(C++) (0)	2022.01.31
[BOJ/Platinum 5] 백준 2505 두 번 뒤집기(C++) (0)	2022.01.30

문제 링크

문제

입력

출력

제한

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

알고리즘 분류

풀이

코드

'BOJ > Platinum ~ Diamond' 카테고리의 다른 글

티스토리툴바