[P5] 백준 20541번 앨범정리 C++ 해시맵, 문자열, 트리, 구현

리뷰

 

앨범이나 사진이 중복될 경우 출력하는 문자열이 잘못되어서 계속 틀렸다... 문제를 잘 읽자 ㅠ

Linked List를 사용한다면 시간을 더 줄일 수 있을 것 같은데 아무래도 해시맵의 키를 경로의 합인 문자열을 사용하다 보니 해시 충돌이 나서 더 이상 시간을 줄이기엔 무리가 있는 것 같다.

해시맵을 통해 절대 경로를 key로 사용하는 방식으로 문제를 풀었다.

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

 

전역 변수

• Data : 앨범 정보를 저장할 구조체, 부모 앨범명, 현재 앨범명, 현재 앨범에 존재하는 앨범 및 사진 집합이 저장된다.
• dic : 맵 구조를 나타낼 해시맵, 앨범 이름을 키로 받고, 해당 폴더 정보 Data 구조체를 값으로 저장한다.
• del_album, del_photo : 삭제한 앨범와 사진의 개수를 저장할 정수형 변수

 

함수

1. dfs

void dfs(string s)

 

1. 앨범 삭제 시 하위 앨범 및 사진을 삭제하는 함수
2. 매개변수 s를 키로 갖는 앨범 정보를 입력 받는다.
3. 현재 앨범에 존재하는 앨범과 사진의 개수를 각각의 변수에 더해준다.
4. 하위 앨범명을 dfs의 인자로 넘겨주어 깊이 우선 탐색을 재귀로 진행해 준다.
5. 하위 앨범을 모두 탐색했다면 현재 앨범을 맵에서 삭제해 준다.

 

문제풀이

1. 루트 앨범은 album이므로 현재 위치를 나타낼 cur을 album으로 초기화 해준다.
2. 루트 앨범의 정보를 초기화 해준다, 루트 앨범의 경우 부모가 자기 자신인 상태이다.
3. 쿼리의 개수 q를 입력 받아주고 q만큼의 반복문을 시작해 준다.
4. 명령어와 인자를 order, arg로 입력 받아주고 각 명령에 맞는 구현해 준다.
5. 우선 대부분의 명령이 현재 앨범 정보를 포함해야 하므로 cur을 키값으로 갖는 앨범을 Data타입으로 불러와 준다.
6. arg가 S일 경우 참조할 새로운 경로를 의미하므로 new_path 문자열에 cur + arg를 더한값을 초기화 해준다.
7. mkalb : 현재 앨범에서 앨범을 새로 만들어준다, 현재 앨범의 albums에 arg를 추가하고 new_path로 맵정보를 초기화
8. 생성하고자 하는 폴더가 이미 존재한다면 duplicated album name을 출력해 준다.
9. rmalb : 현재 앨범에서 앨범을 삭제해 준다. 각 arg에 맞게 앨범 정보를 dfs에 인자로 전달하고 재귀를 진행한다.
10. insert : 현재 앨범에 사진을 추가해 준다, 이미 존재한다면 duplicated photo name을출력해 준다.
11. delete : 현재 앨범에서 사진을 삭제해 준다, 해당 작업은 재귀가 필요하지 않다.
12. ca : 다른 앨범으로 이동한 뒤 현재 위치한 앨범을 출력한다, 각 arg에 맞게 진행하면 된다.

 

참고 사항

• 이미 앨범이나 사진이 존재한다면 "duplicated album/photo name"을 출력해 주어야 한다. (폴더/사진 변수명 X)
• 연결 리스트를 사용하여 구현하는게 해시맵과 집합만 사용하는 구현보다 더 빠르다.
• 각 order마다 함수를 사용하여 구현하는 것이 디버깅에 더 도움이 되는 것 같다.
• 집합은 정렬이 필요하므로 set을 사용하고, 경로를 절대참조 하므로 맵은 unordered_map을 사용해 주면 된다.

 

 

정답 코드

#include<iostream>
#include<unordered_map>
#include<set>

using namespace std;

struct Data { // 앨범 정보를 저장할 구조체
	string par; // 부모 앨범명
	string cur; // 현재 앨범명
	set<string> albums; // 현재 앨범에 존재하는 하위 앨범명의 집합
	set<string> photos; // 현재 앨범에 존재하는 사진명의 집합
};

unordered_map<string, Data> dic;
int del_album = 0, del_photo = 0; // 삭제 정보 저장용

void dfs(string s) { // 앨범 삭제 시 진행할 재귀, 현재 앨범명을 매개변수로 받는다.
	set<string>& albums = dic[s].albums; // 현재 앨범의 하위 앨범 집합
	set<string>& photos = dic[s].photos; // 현재 앨범의 사진 집합
	del_album += albums.size(); // 앨범의 개수만큼 더해준다.
	del_photo += photos.size(); // 사진의 개수만큼 더해준다.
	for (string album : albums) dfs(album); // 하위 앨범 재귀 진행
	dic.erase(s); // 현재 앨범를 맵에서 삭제
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	string cur = "album"; // 루트 앨범
	dic[cur] = { "album", "album", {}, {} }; // 루트 앨범 초기화, 부모는 자기 자신
	int q; cin >> q;
	while (q--) {
		string order, arg; cin >> order >> arg; // 명령어, 쿼리
		string new_path = cur + arg; // 새로운 경로, 현재 폴더명 + 입력값 (입력값이 S일때만 사용)
		Data& data = dic[cur]; // 현재 앨범 참조
		if (order == "mkalb") { // 1. 앨범 생성
			set<string>& albums = data.albums; // 현재 앨범 정보 참조
			if (albums.find(new_path) == albums.end()) { // 현재 앨범에 생성하고자 하는 앨범이 없으면
				albums.insert(new_path); // 앨범 추가 (앨범 명 : 현재 앨범 + 앨범 명)
				dic[new_path] = { cur, arg, {}, {} }; // 생성된 앨범 초기화
			}
			else cout << "duplicated album name\n"; // 중복 존재 시
		}
		else if (order == "rmalb") { // 2. 앨범 삭제
			del_album = 0, del_photo = 0; // 초기값 할당
			set<string>& albums = data.albums; // 현재 앨범 정보 참조
			if (!albums.empty()) { // 앨범이 있을때
				del_album = 1; // 기본 1개 삭제
				if (arg == "-1") { // 사전순 가장 앞쪽 앨범 삭제
					string tar = *albums.begin();
					dfs(tar); // 해당 앨범의 하위 앨범 삭제
					albums.erase(tar); // 현재 앨범에서 해당 앨범 삭제
					dic.erase(tar); // 맵에서 해당 앨범 삭제
				}
				else if (arg == "1") { // 사전순 가장 뒤족 앨범 삭제
					string tar = *albums.rbegin();
					dfs(tar);
					albums.erase(tar);
					dic.erase(tar);
				}
				else if (arg == "0") { // 현재 앨범의 모든 앨범 삭제
					del_album = albums.size(); // 삭제한 개수 최신화
					for (string album : albums) {
						dfs(album);
						dic.erase(album);
					}
					albums.clear(); // 앨범 초기화
				}
				else { // 특정 앨범 삭제
					if (albums.find(new_path) != albums.end()) { // 해당 앨범명이 있는지 체크
						dfs(new_path);
						albums.erase(new_path);
						dic.erase(new_path);
					}
					else del_album = 0; // 일치하는 앨범이 없으면 삭제한 개수 0으로 변경
				}
			}
			cout << del_album << " " << del_photo << "\n"; // 삭제한 앨범 및 사진 파일 개수 출력
		}
		else if (order == "insert") { // 사진을 현재 앨범에 추가한다.
			set<string>& photos = data.photos;
			if (photos.find(new_path) == photos.end()) photos.insert(new_path); // 중복 여부 체크
			else cout << "duplicated photo name\n"; // 중복 시 출력
		}
		else if (order == "delete") { // 현재 앨범에서 특정 사진을 삭제한다.
			del_photo = 0; // 삭제한 개수 초깃값
			set<string>& photos = data.photos;
			if (!photos.empty()) { // 사진이 있을때
				del_photo = 1; // 기본 1개 삭제
				if (arg == "-1") photos.erase(photos.begin()); // 사전순 가장 앞쪽 사진 삭제
				else if (arg == "1") photos.erase(--photos.end()); // 사전순 가장 뒤쪽 사진 삭제
				else if (arg == "0") { // 존재하는 모든 사진 삭제
					del_photo = photos.size(); // 삭제한 개수 최신화
					photos.clear();
				}
				else { // 특정 이름의 사진 삭제
					if (photos.find(new_path) != photos.end()) photos.erase(new_path); // 존재하는지 여부 체크
					else del_photo = 0; // 일치하는 사진이 없으면 삭제한 개수 0으로 변경
				}
			}
			cout << del_photo << "\n"; // 삭제한 개수 출력
		}
		else { // 앨범 이동
			if (arg == "..") cur = data.par; // 상위 앨범로 이동
			else if (arg == "/") cur = "album"; // 루트 앨범로 이동
			else { // 현재 앨범에 존재하는 특정 앨범로 이동
				set<string>& albums = data.albums;
				if (albums.find(new_path) != albums.end()) cur = new_path;
			}
			cout << dic[cur].cur << "\n"; // 이동 작업 후 현재 앨범의 이름 출력
		}
	}
}