[백준 20541] 앨범 정리

작성일 | In |

문제 링크

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

풀이

앨범을 관리하기 위해 구조체를 이용했습니다.

구조체는 부모 노드(앨범)의 포인터, 이름, 자식 노드(앨범)가 들어있는 map, 사진이 들어있는 set, 현재 앨범에 들어있는 앨범의 개수(누적), 현재 앨범에 들어있는 사진의 개수(누적)으로 이루어져 있습니다.

  1. mkalb 명령어를 받는다면 map에 앨범을 생성합니다.

  2. rmalb

    2-1. $S$ : 앨범 안의 앨범 개수, 사진 개수를 출력하고 map 에서 $S$를 지웁니다.

    2-2. -1 : *map.begin() 안의 앨범 개수, 사진 개수를 출력하고 map에서 map.begin()을 지웁니다.

    2-3. 0 : 현재 앨범안의 앨범 개수, 사진 개수 - set.size()를 출력하고 map을 clear합니다.

    2-4. 1 : *(prev(map.end())) 안의 앨범 개수, 사진 개수를 출력하고 map에서 prev(map.end())을 지웁니다.

  3. insert 명령어를 받는다면 set에 사진을 생성합니다.

  4. delete

    4-1. $S$ : 1을 출력하고 set 에서 $S$를 지웁니다.

    4-2. -1 : 1을 출력하고 set에서 set.begin()을 지웁니다.

    4-3. 0 : set.size()를 출력하고 set을 clear합니다.

    4-4. 1 : 1을 출력하고 set에서 prev(set.end())을 지웁니다.

  5. ca

    5-1. $S$ : 현재 포인터를 map[$S$] 로 옮깁니다.

    5-2. .. : 현재 포인터를 부모 포인터로 옮깁니다.

    5-3. / : 부모 포인터가 null pointer 일때까지 현재 포인터를 부모 포인터로 옮깁니다. 나이브하게 부모로 올라가게 구해도 ca $S$로 내려오는 횟수가 최대 $O(Q)$번이기 때문에 올라가는 횟수 또한 $O(Q)$입니다.

생성 / 제거 / 이동을 할때마다 현재 포인터에서의 누적 앨범 개수 / 누적 사진 개수를 잘 관리하면 빠른 시간내로 문제를 풀 수 있습니다. 쿼리마다 드는 가장 무거운 연산이 map/set에서 하는 $O(\log Q)$ 연산이므로 시간복잡도는 $O(Q \log Q)$입니다. 자세한 구현은 코드를 참고해주세요.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct album{
    album *p;
    string name;
    map<string, album> mp;
    set<string> st;
    int as, ps;
}root;

int q;
string t, s;

void rmalb(album* u, int a, int b){
    cout << a << " " << b << "\n";
    u->as = u->as - a, u->ps = u->ps - b;
}

void del(album* u, int a){
    cout << a << "\n";
    u->ps -= a;
}

void up(album* &u){
    album* p = u->p;
    p->as += u->as+1, p->ps += u->ps;
    u = p;
}

void down(album* &u, album* x){
    u->as -= x->as+1, u->ps -= x->ps;
    u = x;
}

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

    album* u = &root;
    root.p = NULL, root.name = "album";

    cin >> q;
    while(q--){
        cin >> t;
        if(t == "mkalb"){
            cin >> s;
            if(u->mp.count(s)){
                cout << "duplicated album name\n";
            }else{
                u->as += 1;
                album* x = &(u->mp[s]);
                x->p = u, x->name = s;
            }
        }else if(t == "rmalb"){
            cin >> s;
            if(u->mp.empty()){
                rmalb(u, 0, 0);
            }else if(s == "0"){
                rmalb(u, u->as, u->ps - u->st.size());
                u->mp.clear();
            }else if(s == "1"){
                album* x = &((*prev(u->mp.end())).second);
                rmalb(u, x->as+1, x->ps);
                u->mp.erase(prev(u->mp.end()));
            }else if(s == "-1"){
                album* x = &((*(u->mp.begin())).second);
                rmalb(u, x->as+1, x->ps);
                u->mp.erase(u->mp.begin());
            }else if(u->mp.count(s)){
                album* x = &((*(u->mp.find(s))).second);
                rmalb(u, x->as+1, x->ps);
                u->mp.erase(u->mp.find(s));
            }else{
                rmalb(u, 0, 0);
            }
        }else if(t == "insert"){
            cin >> s;
            if(u->st.count(s)){
                cout << "duplicated photo name\n";
            }else{
                u->st.insert(s), u->ps += 1;
            }
        }else if(t == "delete"){
            cin >> s;

            if(u->st.empty()){
                del(u, 0);
            }else if(s == "0"){
                del(u, u->st.size());
                u->st.clear();
            }else if(s == "1"){
                del(u, 1);
                u->st.erase(prev(u->st.end()));
            }else if(s == "-1"){
                del(u, 1);
                u->st.erase(u->st.begin());
            }else if(u->st.count(s)){
                del(u, 1);
                u->st.erase(s);
            }else{
                del(u, 0);
            }
        }else if(t == "ca"){
            cin >> s;
            if(s == ".."){
                if(u->p != NULL) up(u);
            }else if(s == "/"){
                while(u->p != NULL) up(u);
            }else{
                if(u->mp.count(s)) down(u, &(u->mp[s]));
            }
            cout << u->name << "\n";
        }
    }
}