백준 문제 20541번 앨범정리 문제풀이 c++

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

20541번: 앨범정리

 

코드

//20541번
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;

class Album
{
private:
    Album* parentAlbum;
    string albumName;
    int photoCnt;
    int albumCnt;
    set <string> photoSet;  //사진이름
    map <string, Album*> albumMap;   //자식 앨범이름 , 자식 앨범 클래스
 


public:
    Album(Album* inputparentAlbum, string inputAlbumName){parentAlbum=inputparentAlbum; albumName = inputAlbumName;}
    void deleteAlbum();
    Album* getParentAlbum(){return parentAlbum;}
    string getAlbumName(){return albumName;}
    void setAlbumCnt();
    int getAlbumCnt(){return albumCnt;}
    void setPhotoCnt();
    int getPhotoCnt(){return photoCnt;}
    void mkalbFunc(string inputAlbumName);
    void rmalbFunc(string inputAlbumName);
    void insertFunc(string inputPhotoName);
    void deleteFunc(string inputPhotoName);
    void caFunc(string inputalbumNmae);
};

Album* curAlbum;
Album* topAlbum;

void Album::setAlbumCnt()
{
    albumCnt = 0;
    if(albumMap.size() == 0)
    {
        return;
    }
    else
    {
        for(auto it = albumMap.begin(); it != albumMap.end(); it++)
        {
            albumCnt++;
            (*it->second).setAlbumCnt();
            albumCnt = albumCnt + (*it->second).getAlbumCnt();
        }
    }
}

void Album::setPhotoCnt()
{
    photoCnt = 0;
    if(albumMap.empty())
    {
        photoCnt = photoCnt + photoSet.size();
        return;
    }
    else
    {
        photoCnt = photoCnt + photoSet.size();
        for(auto it = albumMap.begin(); it != albumMap.end(); it++)
        {
            (*it->second).setPhotoCnt();
            photoCnt = photoCnt + (*it->second).getPhotoCnt();
        }
    }
}

void Album::mkalbFunc(string inputAlbumName)
{
    if(albumMap.count(inputAlbumName) == 0) //중복 아님
    {
        Album *album = new Album(curAlbum, inputAlbumName);
        curAlbum->albumMap.insert({inputAlbumName, album});
    }
    else
    {
        cout<<"duplicated album name\n";
    }
}

void Album::deleteAlbum()
{
    delete this;
}

void Album::rmalbFunc(string inputAlbumName)
{
    int deletePhotoCnt = 0;
    int deleteAlbumCnt = 0;
    if(inputAlbumName == "-1")
    {
        if(albumMap.size() != 0)
        {
            auto it = curAlbum->albumMap.begin();

            (*it->second).setPhotoCnt();
            (*it->second).setAlbumCnt();

            deletePhotoCnt = deletePhotoCnt + (*it->second).getPhotoCnt();
            deleteAlbumCnt = deleteAlbumCnt + (*it->second).getAlbumCnt();
            
            (*it->second).photoSet.clear();
            (*it->second).deleteAlbum();

            deleteAlbumCnt++;
            albumMap.erase(it);
        }
    }
    else if(inputAlbumName == "0")
    {
        for(auto it = curAlbum->albumMap.begin(); it != curAlbum->albumMap.end(); it++)
        {
            (*it->second).setPhotoCnt();
            (*it->second).setAlbumCnt();

            deletePhotoCnt = deletePhotoCnt + (*it->second).getPhotoCnt();
            deleteAlbumCnt = deleteAlbumCnt + (*it->second).getAlbumCnt();

            (*it->second).photoSet.clear();
            (*it->second).deleteAlbum();

            deleteAlbumCnt++;

        }
        albumMap.clear();
    }
    else if(inputAlbumName == "1")
    {
        if(albumMap.size() != 0)
        {
            auto it = curAlbum->albumMap.end();
            it--;

            (*it->second).setPhotoCnt();
            (*it->second).setAlbumCnt();

            deletePhotoCnt = deletePhotoCnt + (*it->second).getPhotoCnt();
            deleteAlbumCnt = deleteAlbumCnt + (*it->second).getAlbumCnt();

            (*it->second).photoSet.clear();
            (*it->second).deleteAlbum();

            deleteAlbumCnt++;
            albumMap.erase(it);
        }
    }
    else
    {
        if(curAlbum->albumMap.count(inputAlbumName) != 0)
        {
            auto it = curAlbum->albumMap.find(inputAlbumName);

            (*it->second).setPhotoCnt();
            (*it->second).setAlbumCnt();

            deletePhotoCnt = deletePhotoCnt + (*it->second).getPhotoCnt();
            deleteAlbumCnt = deleteAlbumCnt + (*it->second).getAlbumCnt();

            (*it->second).photoSet.clear();
            (*it->second).deleteAlbum();

            deleteAlbumCnt++;
            albumMap.erase(it);
        }
    }
    cout<<deleteAlbumCnt<<" "<<deletePhotoCnt<<"\n";
}

void Album::insertFunc(string inputPhotoName)
{
    if(photoSet.count(inputPhotoName) == 0) //중복 아님
    {
        curAlbum->photoSet.insert(inputPhotoName);
    }
    else
    {
        cout<<"duplicated photo name\n";
    }
}

void Album::deleteFunc(string inputPhotoName)
{
    int deletePhotoCnt = 0;
    if(inputPhotoName == "-1")
    {
        if(photoSet.size()!=0)
        {
            auto it = photoSet.begin();

            deletePhotoCnt = 1;

            curAlbum->photoSet.erase(it);
        }
    }
    else if(inputPhotoName == "0")
    {
        deletePhotoCnt = deletePhotoCnt + curAlbum->photoSet.size();

        curAlbum->photoSet.clear();
    }
    else if(inputPhotoName == "1")
    {
        if(photoSet.size()!=0)
        {
            auto it = photoSet.end();
            it--;

            deletePhotoCnt = 1;

            curAlbum->photoSet.erase(it);
        }
    }
    else
    {
        auto it = photoSet.find(inputPhotoName);
        if(it != photoSet.end())
        {
            deletePhotoCnt = 1;
            curAlbum->photoSet.erase(it);
        }
    }
    cout<<deletePhotoCnt<<"\n";
}

void Album::caFunc(string inputAlbumName)
{
    if(inputAlbumName == "..")
    {
        if(curAlbum->getAlbumName() != "album")
        {
            curAlbum = curAlbum->getParentAlbum();
        }
    }
    else if(inputAlbumName == "/")
    {
        curAlbum = topAlbum;
    }
    else
    {
        if(curAlbum->albumMap.count(inputAlbumName) != 0)
        {
            curAlbum = curAlbum->albumMap[inputAlbumName];
        }
    }
    
    cout<<curAlbum->getAlbumName()<<"\n";
}


void doTask(string command)
{
    if(command == "mkalb")
    {
        string albumName; cin>>albumName;
        curAlbum->mkalbFunc(albumName);
    }
    else if(command == "rmalb")
    {
        string albumName; cin>>albumName;
        curAlbum->rmalbFunc(albumName);
    }
    else if(command == "insert")
    {
        string photoName; cin>>photoName;
        curAlbum->insertFunc(photoName);
    }
    else if(command == "delete")
    {
        string photoName; cin>>photoName;
        curAlbum->deleteFunc(photoName);
    }
    else if(command == "ca")
    {
        string albumName; cin>>albumName;
        curAlbum->caFunc(albumName);
    }
}

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

    curAlbum = new Album(NULL, "album");
    topAlbum = curAlbum;

    int n; cin>>n;
    for(int i = 0; i < n; i++)
    {
        string command; cin>>command;
        doTask(command);
    }
}

 

문제해석

문제를 읽어보면 앨범은 자식으로 또 다른 앨범과 사진을 가질 수 있는 트리 형태임을 알 수 있다.

그렇다면 이 문제를 풀기 위해서 일단 앨범 클래스가 필요하다.

앨범 클래스는 다음과 같이 정의하였다.

class Album
{
private:
    Album* parentAlbum;
    string albumName;
    int photoCnt;
    int albumCnt;
    set <string> photoSet;  //사진이름
    map <string, Album*> albumMap;   //자식 앨범이름 , 자식 앨범 클래스
 


public:
    Album(Album* inputparentAlbum, string inputAlbumName){parentAlbum=inputparentAlbum; albumName = inputAlbumName;}
    void deleteAlbum();
    Album* getParentAlbum(){return parentAlbum;}
    string getAlbumName(){return albumName;}
    void setAlbumCnt();
    int getAlbumCnt(){return albumCnt;}
    void setPhotoCnt();
    int getPhotoCnt(){return photoCnt;}
    void mkalbFunc(string inputAlbumName);
    void rmalbFunc(string inputAlbumName);
    void insertFunc(string inputPhotoName);
    void deleteFunc(string inputPhotoName);
    void caFunc(string inputalbumNmae);
};

 

attribute 먼저 차근차근 설명해보겠다.

Album* parentAlbum;

명령어가 ca .. 일 때 상위 앨범으로 이동해야 하므로 부모 앨범의 정보를 가지고 있어야 한다.

 

 

string albumName;

문제에서 앨범의 이름으로 검색을 하므로 자기 자신의 앨범의 이름이 필요하다.

 

 

int photoCnt;
int albumCnt;

현재 앨범이 자식으로 가지고 있는 총 사진의 개수와 총 앨범의 개수가 필요하다.

 

예를 들어 위와 같은 상황이고 현재 앨범이 Album1이라면 photoCnt의값은 5가 되고 albumCnt의 값은 3이 된다.

 

set <string> photoSet;  //사진이름
map <string, Album*> albumMap;   //자식 앨범이름 , 자식 앨범 클래스

요구사항에서 rmalb 또는 delete 일 때 사전 순으로 가장 빠른 또는 가장 늦은 앨범 또는 사진을 삭제해야 하는 상황이다.
그렇다면 매번 rmalb 또는 delete가 입력될 때마다 정렬하는 것은 매우 비효율적이기 때문에 자동 정렬이 되는 set과 map을 사용하였다.
또한 이 set과 map은 size() 함수를 이용하여 현재 앨범의 직속 자식의 사진 수와 앨범 수를 얻어낼 수 있다.

이 그림에서 현재 앨범이 Album1이라면 직속 자식이면서 사진인 녀석은 Photo1 1개이고 

직속 자식이면서 앨범인 녀석은 Album2, Album3으로 2개이다.

 

 

이번엔 클래스의 메소드를 살펴보면

public:
    Album(Album* inputparentAlbum, string inputAlbumName){parentAlbum=inputparentAlbum; albumName = inputAlbumName;}
    void deleteAlbum();
    Album* getParentAlbum(){return parentAlbum;}
    string getAlbumName(){return albumName;}
    void setAlbumCnt();
    int getAlbumCnt(){return albumCnt;}
    void setPhotoCnt();
    int getPhotoCnt(){return photoCnt;}
    void mkalbFunc(string inputAlbumName);
    void rmalbFunc(string inputAlbumName);
    void insertFunc(string inputPhotoName);
    void deleteFunc(string inputPhotoName);
    void caFunc(string inputalbumNmae);

생성자와 get과 set 메소드를 제외하고 mkalb rmalb insert delete ca 명령어에 해당하는 각각의 메소드가 존재한다.
여기서 rmalb을 제외한 4가지는 맨 위의 전체코드만 봐도 아마 쉽게 이해가 갈듯싶어서 설명을 생략할 건데

개인적으로 좀 생각했었던 부분이 rmalb명령어가 들어왔을 때 실행되는 rmalbFunc() 안에서 실행되는 
setPhotoCnt() 와 setAlbumCnt()였기 때문에 이 부분만 설명해보려 한다.

 

setPhotoCnt() 부터 보자

void Album::setPhotoCnt()
{
    photoCnt = 0;
    if(albumMap.empty())
    {
        photoCnt = photoCnt + photoSet.size();
        return;
    }
    else
    {
        photoCnt = photoCnt + photoSet.size();
        for(auto it = albumMap.begin(); it != albumMap.end(); it++)
        {
            (*it->second).setPhotoCnt();
            photoCnt = photoCnt + (*it->second).getPhotoCnt();
        }
    }
}

if에 해당하는 부분이 현재 앨범의 직속 자식 앨범이 없는경우 else에 해당하는 부분이 현재 앨범의 직속 자식 앨범이 있는경우이다.

if의 경우 photoCnt의 값이 당연히 photoSet.size()만큼이 된다.
else의 경우 photoSet.size()뿐만 아니라 직속 자식 앨범을 순차적으로 접근하여 직속 자식의 앨범이 가지고있는 사진의 개수를 순차적으로 더 하는 방식으로 구현하였다.

현재 앨범이 Album1이고 Album1.setPhotoCnt()를 호출하였다면 1 + 2 + 2로 5가 된다.

마치 재귀 함수를 구현하듯이 구현하였고 재귀함수로 보자면 if(albumMap.empty())가 기저 사례의 역할을 한다.

 

그 다음 setAlbumCnt()을보자

void Album::setAlbumCnt()
{
    albumCnt = 0;
    if(albumMap.size() == 0)
    {
        return;
    }
    else
    {
        for(auto it = albumMap.begin(); it != albumMap.end(); it++)
        {
            albumCnt++;
            (*it->second).setAlbumCnt();
            albumCnt = albumCnt + (*it->second).getAlbumCnt();
        }
    }
}

if에 해당하는 부분이 현재 앨범의 직속 자식 앨범이 없는경우 else에 해당하는 부분이 현재 앨범의 직속 자식 앨범이 있는경우이다.

 

if의 경우 albumCnt의 값이 당연히 0이 된다.

else의 경우 자기 자신도 앨범이니까 for문 안에 albumCnt++를 적어주고 앨범을 순차적으로 접근하여 직속 자식의 앨범이 가지고있는 앨범의 개수를 순차적으로 더 하는 방식으로 구현하였다.

현재 앨범이 Album1이고 Album1.setAlbumCnt()를 호출하였다면 1 + 1 + 1로 3이 된다.
setPhotoCnt()와 비슷하게 마치 재귀 함수를 구현하듯이 구현하였고
재귀함수로 보자면 if(albumMap.size() == 0) 혹은 if(albumMap.empty())가 기저 사례의 역할을 한다.

이거 외에 나머지는 뭐 그냥 노가다로 구현하면 되는 거기 때문에 생략..

아 그리고 이 문제 보고 포토 클래스랑 앨범 클래스 두 개 만들어놓고 시작했는데 문제를 다시 읽어보니 사진은 가지고 있는 속성이 사진 이름 하나 뿐이기 때문에 굳이 클래스로 정의하진 않았는데 만약에 사진에 이름 외에 다른 정보들
예를 들어 찍은 날짜, 수정시간, 만든이 등등 속성이 여럿 존재한다면 포토 클래스를 만들어야 할 것이다.

이 문제를 한마디로 말하자면 학교에서 객체지향 프로그래밍 과제 하는 느낌?

꽤 재밌었음