본문 바로가기
코딩일기/PS일기

[BOJ 20541] 앨범정리 C++ 풀이

by 용웅상 2021. 3. 10.

문제 링크

www.acmicpc.net/problem/20541

 

20541번: 앨범정리

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

www.acmicpc.net

풀이

이번 문제는 5개의 쿼리를 구현하는 문제입니다.

단, 자료구조를 구현하는 능력이 요구되는 문제였습니다.

 

1. 문제 접근

문제를 읽어보시면, 우리가 Windows, Linux, iOS등 운영체제에서 사용하는 폴더 체계를 구현하는 문제라는 것을 알 수 있습니다.

저는 이 폴더의 구조를 struct node로 구현하여, 아래와 같이 표현하였습니다.

struct node {
	string my_name; //폴더명
	map<string, node*> folder; // 현재 폴더에 속한 하위 폴더
	set<string> picture; // 현재 폴더에 속한 사진
	node* parent = NULL; // 나의 부모 폴더

	int fol_cnt = 0; // 지금 폴더부터 하위 폴더까지 모두가 가진 폴더 수
	int pic_cnt = 0; // 지금 폴더부터 하위 폴더까지 모두가 가진 사진 수
};

node* root;
node* cur;

Struct node는 오른쪽의 윈도우즈 폴더를 구현한 구조체입니다. 

5, 6번은 문제에서 요구하는 삭제 후 삭제된 폴더,사진 수를 편하게 출력하기 위한 카운터입니다.

node *root는 최상위 폴더 album을 가리키는 포인터입니다.

node *cur 현재 접속해있는 폴더를 가리키는 포인터입니다.

 

여기서 사용된 map과 set은 자주 사용되는 C++ STL입니다. 꼭 공부해보시기를 권해드립니다.

 

1) main

    ㄱ. init()함수를 호출, 변수 입력 받기 및 초기화를 진행합니다.

    ㄴ. N번의 쿼리문을 진행하며, 이 쿼리를 처리하는 함수는 solve()입니다.

int main()
{
	init();

	for (int i = 0; i < N; i++)
		solve();

	return 0;
}

 

 

2) init

    ㄱ. 입력 N을 입력받습니다.

    ㄴ. 최상위 폴더인 album을 만들고, node* cur가 album폴더를 가리키게 지정합니다.

void init()
{
	scanf(" %d", &N);

	root = new node;
	root->my_name = "album";
	root->parent = NULL;
	cur = root;

	return;
}

 

 

3) solve

    ㄱ. 두 개의 명령어를 받아들입니다. order은 메인 쿼리문, order2는 하위 쿼리문입니다.

    ㄴ. 문제에서 주어진 5개의 쿼리문을 찾아, 알맞은 쿼리문을 호출하며, 파라미터로 하위 쿼리문을 전달합니다.

void solve()
{
	char order1[7];
	char order2[21];

	scanf(" %s", &order1);
	scanf(" %s", &order2);

	if (strcmp(order1, "mkalb") == 0)
		mkalb(order2);
	else if (strcmp(order1, "rmalb") == 0)
		rmalb(order2);
	else if (strcmp(order1, "insert") == 0)
		my_insert(order2);
	else if (strcmp(order1, "delete") == 0)
		my_delete(order2);
	else if (strcmp(order1, "ca") == 0)
		ca(order2);

	return;
}

 

 

4) mkalb

    ㄱ. 입력된 폴더의 이름을 가진 폴더가 없다?

        참. 새 폴더를 만든다.

        거짓. 중복된 폴더 이름을 출력

void mkalb(char* order2) // make_album
{
	if (cur->folder.find(order2) == cur->folder.end())
	{ //현재 폴더에 입력된 이름을 가진 폴더가 없다면
		node* new_node = make_node(order2); // 새폴더를 만들고
		cur->folder.insert({ order2, new_node }); //현재 폴더에 하위 폴더로 추가
		renewCnt(cur, 1, 1, 0); // strcut의 카운터를 갱신
	}
	else // 현재 폴더에 입력된 이름을 가진 폴더가 있으므로
		printf("duplicated album name\n");

	return;
}

 

 

5) make_node

    새로운 폴더를 만드는 함수입니다.

node* make_node(char* name) // 새로운 폴더 만들기
{
	node* new_node = new node;
	new_node->my_name = name;
	new_node->parent = cur;

	return new_node;
}

 

 

6) renewCnt

    현재 폴더의 정보가 바뀌면 (폴더 추가, 삭제 / 사진 폴더, 추가) struct node에 있는 카운터들을 갱신하는 함수

void renewCnt(node* now, int flag, int folcnt, int piccnt) // 폴더 정보 변화를 갱신
{   
	// flag가 1이면 추가
	// flag가 -1이면 삭제
	node* tmp = now;

	folcnt *= flag;
	piccnt *= flag;

	while (tmp != root)
	{
		tmp->fol_cnt += folcnt;
		tmp->pic_cnt += piccnt;
		tmp = tmp->parent;
	}
	root->fol_cnt += folcnt;
	root->pic_cnt += piccnt;

	return;
}

제가 만든 struct node의 변수인 fol_cnt와 pic_cnt가 현재 폴더부터 모든 하위 폴더의 폴더 수와 사진 수를 가지고 있기 때문에, 현재 폴더부터 root폴더까지 모든 폴더를 갱신해주어야합니다.

이 부분은 struct node를 변형하여 최적화가 더 가능할 것으로 생각됩니다.

 

 

7) rmalb

    ㄱ. 하위 쿼리문이 -1이면

        i) 폴더명이 사전순으로 가장 빠른 폴더 삭제, 카운트 갱신

    ㄴ. 하위 쿼리문이 0이면

        i)모든 폴더 삭제, 카운트 갱신

    ㄷ. 하위 쿼리문이 1이면

        i) 폴더명이 사전순으로 가장 느린 폴더 삭제, 카운트 갱신

    ㄹ. 하위 쿼리문이 폴더명이면

        i) 해당 폴더를 찾아 삭제, 카운트 갱신

    ㅁ. 삭제된 폴더수와 삭제된 사진 수를 출력

void rmalb(char* order2) // remove_album
{
	int del_fol = 0; // 삭제될 폴더 수 기록
	int del_pic = 0; // 삭제될 사진 수 기록

	if (strcmp(order2, "-1") == 0)
	{
		if (cur->folder.size())
		{
			auto now = cur->folder.begin();
			node* del_fold = now->second;
			del_fol = del_fold->fol_cnt + 1;//지금 삭제되는 폴더까지
			del_pic = del_fold->pic_cnt;
			renewCnt(cur, -1, del_fol, del_pic);
			cur->folder.erase(now);
		}
	}
	else if (strcmp(order2, "0") == 0)
	{
		if (cur->folder.size())
		{
			del_fol = cur->folder.size(); // 현재 폴더의 바로 자식 폴더 수

			for (auto now = cur->folder.begin(); now != cur->folder.end(); now++)
			{
				del_fol += now->second->fol_cnt;// 자식폴더가 가지고 있는 폴더수
				del_pic += now->second->pic_cnt;
			}

			renewCnt(cur, -1, del_fol, del_pic);
			cur->folder.clear();
		}
	}
	else if (strcmp(order2, "1") == 0)
	{
		if (cur->folder.size())
		{
			auto now = cur->folder.end();
			now--;
			node* del_fold = now->second;
			del_fol = del_fold->fol_cnt + 1;
			del_pic = del_fold->pic_cnt;
			renewCnt(cur, -1, del_fol, del_pic);
			cur->folder.erase(now);
		}
	}
	else
	{
		auto now = cur->folder.find(order2);
		if (now != cur->folder.end())
		{
			node* del_fold = now->second;
			del_fol = del_fold->fol_cnt + 1;
			del_pic = del_fold->pic_cnt;
			renewCnt(cur, -1, del_fol, del_pic);
			cur->folder.erase(now);
		}
	}

	printf("%d %d\n", del_fol, del_pic);

	return;
}

 

 

8) my_insert

    문제에서 제시된 insert 쿼리문입니다.

    ㄱ. 입력된 사진 이름이 이미 있다면

        i. 중복된 사진 이름 출력

    ㄴ. 입력된 사진 이름이 없다면

        i. 새로운 사진을 만들고, 카운트 갱신

void my_insert(char* order2)
{
	if (cur->picture.find(order2) != cur->picture.end())
	{
		printf("duplicated photo name\n");
	}
	else
	{
		cur->picture.insert(order2);
		renewCnt(cur, 1, 0, 1);
	}
	return;
}

 

 

9) my_delete

    문제에서 제시된 delete 쿼리문입니다.

    ㄱ. 하위 쿼리문이 -1이면

        i) 사진명이 사전순으로 가장 빠른 사진 삭제, 카운트 갱신

    ㄴ. 하위 쿼리문이 0이면

        i)모든 사진 삭제, 카운트 갱신

    ㄷ. 하위 쿼리문이 1이면

        i) 사진명이 사전순으로 가장 느린 사진 삭제, 카운트 갱신

    ㄹ. 하위 쿼리문이 사진명이면

        i) 해당 사진을 찾아 삭제, 카운트 갱신

    ㅁ. 삭제된 사진 수를 출력

void my_delete(char* order2)
{
	int del_pic = 0;
	if (strcmp(order2, "-1") == 0)
	{
		if (cur->picture.size())
		{
			cur->picture.erase(cur->picture.begin());
			del_pic = 1;
			renewCnt(cur, -1, 0, del_pic);
		}
	}
	else if (strcmp(order2, "0") == 0)
	{
		if (cur->picture.size())
		{
			del_pic = cur->picture.size();
			cur->picture.clear();
			renewCnt(cur, -1, 0, del_pic);
		}
	}
	else if (strcmp(order2, "1") == 0)
	{
		if (cur->picture.size())
		{
			auto now = cur->picture.end();
			now--;
			cur->picture.erase(now);
			del_pic = 1;
			renewCnt(cur, -1, 0, del_pic);
		}
	}
	else
	{
		auto now = cur->picture.find(order2);
		if (now != cur->picture.end())
		{
			cur->picture.erase(now);
			del_pic = 1;
			renewCnt(cur, -1, 0, del_pic);
		}
	}

	printf("%d\n", del_pic);
	return;
}

 

 

10) ca

    ㄱ. 하위 쿼리문이 .. 이면

        i. cur가 가리키는 폴더를 내 부모 폴더로 갱신

    ㄴ. 하위 쿼리문이 / 이면

        i. cur가 가리키는 폴더를 최상위 폴더로 (root인 album폴더로) 갱신

    ㄷ. 하위 쿼리문이 폴더명이면

        i. 입력된 폴더명을 가지는 하위 폴더로 cur를 갱신

    ㄹ. 현재 폴더명을 출력

void ca(char* order2) // change_album
{
	if (strcmp(order2, "..") == 0)
	{
		if (cur != root)
			cur = cur->parent;
	}
	else if (strcmp(order2, "/") == 0)
	{
		cur = root;
	}
	else
	{
		auto next = cur->folder.find(order2);
		if (next != cur->folder.end())
			cur = next->second;
	}

	printf("%s\n", cur->my_name.c_str());

	return;
}

 

 

2. 전체 코드

더보기 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <set>

using namespace std;

int N;

struct node {
	string my_name;
	map<string, node*> folder;
	set<string> picture;
	node* parent = NULL;

	int fol_cnt = 0;
	int pic_cnt = 0;
};

node* root;
node* cur;

node* make_node(char* name)
{
	node* new_node = new node;
	new_node->my_name = name;
	new_node->parent = cur;

	return new_node;
}

void renewCnt(node* now, int flag, int folcnt, int piccnt)
{
	// flag가 1이면 추가
	// flag가 -1이면 삭제
	node* tmp = now;

	folcnt *= flag;
	piccnt *= flag;

	while (tmp != root)
	{
		tmp->fol_cnt += folcnt;
		tmp->pic_cnt += piccnt;
		tmp = tmp->parent;
	}
	root->fol_cnt += folcnt;
	root->pic_cnt += piccnt;

	return;
}

void mkalb(char* order2)
{
	if (cur->folder.find(order2) == cur->folder.end())
	{
		node* new_node = make_node(order2);
		cur->folder.insert({ order2, new_node });
		renewCnt(cur, 1, 1, 0);
	}
	else
		printf("duplicated album name\n");

	return;
}

void rmalb(char* order2)
{
	int del_fol = 0;
	int del_pic = 0;

	if (strcmp(order2, "-1") == 0)
	{
		if (cur->folder.size())
		{
			auto now = cur->folder.begin();
			node* del_fold = now->second;
			del_fol = del_fold->fol_cnt + 1;//지금 삭제되는 폴더까지
			del_pic = del_fold->pic_cnt;
			renewCnt(cur, -1, del_fol, del_pic);
			cur->folder.erase(now);
		}
	}
	else if (strcmp(order2, "0") == 0)
	{
		if (cur->folder.size())
		{
			del_fol = cur->folder.size(); // 현재 폴더의 바로 자식 폴더 수

			for (auto now = cur->folder.begin(); now != cur->folder.end(); now++)
			{
				del_fol += now->second->fol_cnt;// 자식폴더가 가지고 있는 폴더수
				del_pic += now->second->pic_cnt;
			}

			renewCnt(cur, -1, del_fol, del_pic);
			cur->folder.clear();
		}
	}
	else if (strcmp(order2, "1") == 0)
	{
		if (cur->folder.size())
		{
			auto now = cur->folder.end();
			now--;
			node* del_fold = now->second;
			del_fol = del_fold->fol_cnt + 1;
			del_pic = del_fold->pic_cnt;
			renewCnt(cur, -1, del_fol, del_pic);
			cur->folder.erase(now);
		}
	}
	else
	{
		auto now = cur->folder.find(order2);
		if (now != cur->folder.end())
		{
			node* del_fold = now->second;
			del_fol = del_fold->fol_cnt + 1;
			del_pic = del_fold->pic_cnt;
			renewCnt(cur, -1, del_fol, del_pic);
			cur->folder.erase(now);
		}
	}

	printf("%d %d\n", del_fol, del_pic);

	return;
}

void my_insert(char* order2)
{
	if (cur->picture.find(order2) != cur->picture.end())
	{
		printf("duplicated photo name\n");
	}
	else
	{
		cur->picture.insert(order2);
		renewCnt(cur, 1, 0, 1);
	}
	return;
}

void my_delete(char* order2)
{
	int del_pic = 0;
	if (strcmp(order2, "-1") == 0)
	{
		if (cur->picture.size())
		{
			cur->picture.erase(cur->picture.begin());
			del_pic = 1;
			renewCnt(cur, -1, 0, del_pic);
		}
	}
	else if (strcmp(order2, "0") == 0)
	{
		if (cur->picture.size())
		{
			del_pic = cur->picture.size();
			cur->picture.clear();
			renewCnt(cur, -1, 0, del_pic);
		}
	}
	else if (strcmp(order2, "1") == 0)
	{
		if (cur->picture.size())
		{
			auto now = cur->picture.end();
			now--;
			cur->picture.erase(now);
			del_pic = 1;
			renewCnt(cur, -1, 0, del_pic);
		}
	}
	else
	{
		auto now = cur->picture.find(order2);
		if (now != cur->picture.end())
		{
			cur->picture.erase(now);
			del_pic = 1;
			renewCnt(cur, -1, 0, del_pic);
		}
	}

	printf("%d\n", del_pic);
	return;
}

void ca(char* order2)
{
	if (strcmp(order2, "..") == 0)
	{
		if (cur != root)
			cur = cur->parent;
	}
	else if (strcmp(order2, "/") == 0)
	{
		cur = root;
	}
	else
	{
		auto next = cur->folder.find(order2);
		if (next != cur->folder.end())
			cur = next->second;
	}

	printf("%s\n", cur->my_name.c_str());

	return;
}

void solve()
{
	char order1[7];
	char order2[21];

	scanf(" %s", &order1);
	scanf(" %s", &order2);

	if (strcmp(order1, "mkalb") == 0)
		mkalb(order2);
	else if (strcmp(order1, "rmalb") == 0)
		rmalb(order2);
	else if (strcmp(order1, "insert") == 0)
		my_insert(order2);
	else if (strcmp(order1, "delete") == 0)
		my_delete(order2);
	else if (strcmp(order1, "ca") == 0)
		ca(order2);

	return;
}

void init()
{
	scanf(" %d", &N);

	root = new node;
	root->my_name = "album";
	root->parent = NULL;
	cur = root;

	return;
}

int main()
{
	init();

	for (int i = 0; i < N; i++)
		solve();

	return 0;
}

질문과 잘못된 정보 수정 요청은 언제나 환영합니다. 편하게 댓글을 달아주세요.

오늘도 부족한 제 글을 읽어주셔서 감사합니다.

'코딩일기 > PS일기' 카테고리의 다른 글

[BOJ 17500] 국경 C++ 풀이  (0) 2021.03.05
[BOJ 10844] 쉬운계단수 C++ 풀이  (3) 2021.02.14
[BOJ 1654] 랜선 자르기 C++ 풀이 // 이분 탐색(이진 탐색) 설명  (0) 2021.02.10
[BOJ 14651] 걷다보니 신천역 삼 (Large) C++ 풀이  (0) 2021.02.09
[BOJ 2240] 자두나무 C++ 풀이  (0) 2021.02.09

관련글

티스토리툴바