20541번: 앨범정리
지혜는 컴퓨터에 있는 사진들을 정리하기 위해 앨범정리 프로그램을 만들었다. 지혜가 만든 앨범정리 프로그램은 기본적으로 "album" 앨범이 존재하며 "album" 앨범은 절대로 삭제할 수 없다.
www.acmicpc.net
문제 확인
알고리즘이 필요 없는 구현 문제입니다.
풀이
주어진 문제대로 구현을 하면 간단하게 풀 수 있습니다.
앨범, 사진 모두 중복이 허용되지 않으므로 앨범은 map, 사진은 set 컨테이너를 활용해서 관리합니다.
주의해야 할 것은 rmalb을 구현할 때 앨범을 삭제하면 하위 앨범 모두 삭제가 되어 삭제한 앨범수 = 1 + 삭제할 앨범의 모든 하위 앨범, 삭제한 사진 수 = 하위 앨범들의 사진 수 가 됩니다.
이를 위해 트리 탐색을 하면 많은 시간이 걸리므로 하위 앨범의 앨범 개수, 사진 개수를 기록해둘 변수를 따로 관리하여야 합니다.
ca 함수를 구현하기 위해 parent를 가르키는 포인터를 가지고 있어야 합니다.
코드
|
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
typedef struct node {
string name;
int alb_count, pic_count;//자식들의 개수 관리
map<string, node*> child;
set<string> pic;
node *parent;
node(string s, node *p) :name(s), parent(p), alb_count(0), pic_count(0) {};
}node;
inline void mkalb(node *cur, string &s) {
auto t = cur->child.lower_bound(s);
if (t == cur->child.end() || t->first != s) {
cur->child.emplace_hint(t, s, new node(s, cur));
while (cur != NULL) {//부모노드 반영
cur->alb_count++;
cur = cur->parent;
}
}
else
cout << "duplicated album name\n";
}
inline void rmalb(node *cur, string &s) {
if (cur->child.empty()) {
cout << "0 0\n";
return;
}
int ta, tp;
if (s == "-1") {
auto t = cur->child.begin();
ta = t->second->alb_count + 1, tp = t->second->pic_count;
cur->child.erase(t);
}
else if (s == "0") {
ta = cur->alb_count, tp = cur->pic_count - cur->pic.size();
cur->child.clear();
}
else if (s == "1") {
auto t = --(cur->child.end());
ta = t->second->alb_count + 1, tp = t->second->pic_count;
cur->child.erase(t);
}
else {
auto t = cur->child.find(s);
if (t == cur->child.end()) {
cout << "0 0\n";
return;
}
ta = t->second->alb_count + 1, tp = t->second->pic_count;
cur->child.erase(t);
}
cout << ta << ' ' << tp << '\n';
while (cur != NULL) {//부모 반영
cur->alb_count -= ta;
cur->pic_count -= tp;
cur = cur->parent;
}
}
inline void insert(node *cur, string &s) {
auto t = cur->pic.lower_bound(s);
if (t == cur->pic.end() || *t != s) {
cur->pic.emplace_hint(t, s);
while (cur != NULL) {//부모 반영
cur->pic_count++;
cur = cur->parent;
}
}
else
cout << "duplicated photo name\n";
}
inline void del(node *cur, string &s) {
if (cur->pic.empty()) {
cout << "0\n";
return;
}
int tp;
if (s == "-1") {
tp = 1;
cur->pic.erase(cur->pic.begin());
}
else if (s == "0") {
tp = cur->pic.size();
cur->pic.clear();
}
else if (s == "1") {
tp = 1;
cur->pic.erase(--(cur->pic.end()));
}
else {
auto t = cur->pic.find(s);
if (t == cur->pic.end()) {
cout << "0\n";
return;
}
tp = 1;
cur->pic.erase(t);
}
cout << tp << '\n';
while (cur != NULL) {//부모 반영
cur->pic_count -= tp;
cur = cur->parent;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
node *root = new node(string("album"), NULL), *cur = root;
int n;
string op, f;
cin >> n;
while (n--) {
cin >> op >> f;
if (op == "mkalb") {
mkalb(cur, f);
}
else if (op == "rmalb") {
rmalb(cur, f);
}
else if (op == "insert") {
insert(cur, f);
}
else if (op == "delete") {
del(cur, f);
}
else if (op == "ca") {
if (f == ".."&& cur != root)
cur = cur->parent;
else if (f == "/" && cur != root)
cur = root;
else {
auto t = cur->child.find(f);
if (t != cur->child.end())
cur = t->second;
}
cout << cur->name << '\n';
}
}
}
|
cs |
반응형
'알고리즘 문제 > [백준]' 카테고리의 다른 글
| [백준] 1915 가장 큰 정사각형 (0) | 2021.02.22 |
|---|---|
| [백준] 1126 같은 탑 (0) | 2021.02.20 |
| [백준] 16225 제271회 웰노운컵 (0) | 2021.02.16 |
| [백준] 2879 코딩은 예쁘게 (0) | 2021.02.14 |
| [백준] 1016 제곱 ㄴㄴ수 (0) | 2021.02.12 |