제한시간: 5000 ms 메모리제한: 256 MB
여러 분은 인터넷 카페 관리자이다.
회원들의 카페 활동 참여도를 분석 하고자한다.
회원들의 참여도가 낮은 그룹과 높은 그룹으로 나누어 분석할 예정이다.
회원 id와 참여도 frequency를 입력받아 아래 사용자 함수를 작성하는 프로그램을 작성하시오.
[해야할 일]
1. 초기 회원수와 회원정보를 전달받아 초기화 : void userInit(int memberCount, Member members[])
2. 목록에 회원 추가 : void addMember(Member obj)
3. 목록 변경 :
목록의 특정 회원(들)을 삭제하고 새로운 회원을 추가한다. (main code 참조)
삭제는 아래 3가지 경우가 있다.
mode == 0 : 참여도가 가장 낮은 회원을 목록에서 제거한다.
참여도가 같은 회원이 여러명인 경우 id가 최소인 회원을 제거하고
그 회원의 id를 반환한다.
mode == 1 : 참여도가 중간인 회원을 목록에서 제거한다.
참여도가 같은 회원이 여러명인 경우 id가 중간인 회원을 제거한다.
목록의 회원수가 짝수명일 경우 중간의 2명을 제거한다.
제거된 회원(들)의 id(의 합)를(을) 반환한다.
mode == 2 : 참여도가 가장 높은 회원을 목록에서 제거한다.
참여도가 같은 회원이 여러명인 경우 id가 최대인 회원을 제거하고
그 회원의 id를 반환한다.
4. 두 그룹의 참여도 총합 구하기 void getSum(int sum[])
각 그룹의 참여도 합을 구하여 sum에 저장한다. 참여도의 합은 int범위이다.
현재 회원수가 홀수인 경우 정중앙 회원의 참여도는 참여도 합에서 제외한다.
sum[0] : 참여도가 낮은 그룹의 참여도 총합
sum[1] : 참여도가 높은 그룹의 참여도 총합
sol.cpp
|
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
153
154
|
struct Member {
int id, frequency;
};
Member mb[50010];
const int LM = (int)1e5;
int freq[LM + 5], active[LM + 5]; //각 id당 참여도배열, 각 id당 삭제됬는지 유무 배열
int fcnt, fsum, bcnt, bsum;
bool Max(int aid, int bid) {
if (freq[aid] != freq[bid])
return freq[aid] > freq[bid];
return aid > bid;
}
bool Min(int aid, int bid) {
if (freq[aid] != freq[bid])
return freq[aid] < freq[bid];
return aid < bid;
}
inline void swap(int& a, int& b) { int t = a; a = b; b = t; }
struct PriorityQueue {
int heap[LM + 5];
int hn;
bool(*comp)(int, int);
void init(int flag) {
hn = 0;
comp = flag ? Max : Min;
}
int size() { return hn;}
bool empty() { return hn == 0;}
int top() {
while (hn && active[heap[1]] == 0)
pop();
return heap[1];
}
void push(int id) {
heap[++hn] = id;
int c = hn;
for (; c > 1 && comp(heap[c], heap[c / 2]); c /= 2) {
swap(heap[c], heap[c/2]);
}
}
void pop() {
swap(heap[1], heap[hn--]);
int p = 1, c = 2;
for (; c <= hn; p = c, c *= 2) {
if (c < hn && comp(heap[c + 1], heap[c]))
c++;
if (!comp(heap[c], heap[p]))
break;
swap(heap[c], heap[p]);
}
}
}minpq, front, back, maxpq; //낮은min, 낮은max, 높은min, 높은max
void addMember(Member obj) { //목록에 회원 추가
int id = obj.id;
active[id] = 1;
freq[id] = obj.frequency;
minpq.push(id);
maxpq.push(id);
front.top();
back.top();
if (fcnt + bcnt == 0 || Min(id, front.top())) { //참여도 낮은 그룹에 해당
front.push(id);
fcnt++;
fsum += obj.frequency;
}
else { //참여도 높은 그룹에 해당
back.push(id);
bcnt++;
bsum += obj.frequency;
}
//ballancing
if (fcnt > bcnt + 1) {
id = front.top();
front.pop();
fcnt--;
fsum -= freq[id];
back.push(id);
bcnt++;
bsum += freq[id];
}
if (fcnt < bcnt) {
id = back.top();
back.pop();
bcnt--;
bsum -= freq[id];
front.push(id);
fcnt++;
fsum += freq[id];
}
}
int removeMembers(int mode) { // 목록 변경
int sid = 0, eid = 0;
if (mode == 0) { //참여도가 가장 낮은 회원 제거
sid = minpq.top();
minpq.pop();
active[sid] = 0;
fcnt--;
fsum -= freq[sid];
}
else if (mode == 1) { //참여도가 중간인 회원 제거
if (fcnt == bcnt) { //회원수가 짝수명일 경우 중간 2명 제거
eid = back.top();
back.pop();
active[eid] = 0;
bcnt--;
bsum -= freq[eid];
}
sid = front.top();
front.pop();
active[sid] = 0;
fcnt--;
fsum -= freq[sid];
}
else if (mode==2) { //참여도가 가장 높은 회원 제거
eid = maxpq.top();
maxpq.pop();
active[eid] = 0;
bcnt--;
bsum -= freq[eid];
}
return sid + eid;
}
void getSum(int sum[]) { //두 그룹의 참여도 총합
sum[0] = fsum;
sum[1] = bsum;
if (fcnt > bcnt) { //회원수가 홀수라면
int id = front.top();
sum[0] -= freq[id];
}
}
void userInit(int memberCount, Member members[]) {
register int i;
fcnt = fsum = bcnt = bsum = 0;
for (i = 0; i < LM; i++) active[i] = freq[i] = 0;
minpq.init(0);
back.init(0);
front.init(1);
maxpq.init(1);
for (i = 0; i < memberCount; i++) {
addMember(members[i]);
}
}
|
cs |
'알고리즘 문제풀이' 카테고리의 다른 글
| SSD에 파일을 쓰기, 삭제, 읽기, 수정하는 프로그램 구현 (0) | 2020.10.31 |
|---|---|
| [CS] Merge Sort (0) | 2020.10.07 |
| [CS] Quick Sort (0) | 2020.10.07 |
| [CS] Stack, Queue (Heap기반) (0) | 2020.10.07 |
| [CS] Stack, Queue(Linear, Circular) (0) | 2020.10.07 |