[코드트리] 코드트리 메신저 (삼성 SW 역량테스트 2023 하반기 오전 2번, B형)
2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,
A형 1문제 + B형 문제 1문제가 출제됩니다.
https://www.codetree.ai/training-field/frequent-problems/problems/codetree-messenger
Define을 다음과 같이 정의한다.
ALARM_OFF는 알람 설정이 OFF일 때, 모든 알림을 더 이상 위로 올려 보내지 않는 경우에 사용한다.
#define MAX (100000 + 5000)
#define DEPTH (20 + 3)
#define READY (100)
#define ALARM_ON_OFF (200)
#define SET_AUTH (300)
#define CHANGE (400)
#define RETRIEVE (500)
#define ALARM_OFF (0)
#define ALARM_ON (1)
NODE는 다음과 같이 정의한다.
parent - 채팅방의 부모
auth - 채팅방의 권한
alarm - 해당 채팅방의 alarm on / off 여부
alarmCount - 해당 채팅방이 알림을 받을 수 있는 채팅방 수
effect[] - 해당 채팅방이 전달할 수 있는 알림의 영향력, effect[3] = 4라면 위로 3개까지 전달할 수 있는 알림이 4개
typedef struct st
{
int parent;
int auth;
int alarm;
int alarmCount;
int effect[DEPTH];
}NODE;
NODE tree[MAX];
effect가 필요한 이유는 알림을 받을 수 있는 채팅방 수 조회 명령의 경우,
매번 알림 상태가 바뀔 때마다 미리 effect로 alarmCount를 갱신해야 O(1)만에 답을 출력할 수 있기 때문이다.
사내 메신저 준비
input에서 입력을 받고, 초기 채팅방 상태를 갱신해야 한다.
문제에서 이진트리의 깊이는 20이하라고 하였으므로, auth가 20보다 큰 입력은 20으로 변경하였다.
void input()
{
for (int i = 0; i <= N; i++)
{
tree[i].alarm = ALARM_ON;
tree[i].alarmCount = 0;
}
for (int i = 1; i <= N; i++) scanf("%d", &tree[i].parent);
for (int i = 1; i <= N; i++)
{
int auth;
scanf("%d", &auth);
if (auth > 20) auth = 20;
tree[i].auth = auth;
}
for (int i = 1; i <= N; i++) initAlarmSetting(i, tree[i].auth);
}
initAlarmSetting의 원리는 다음과 같다.
아래 그림에서 8번 노드의 auth가 3이라면, 8번 노드는 위로 3개의 노드까지 영향을 미친다.
그리고 8번 노드의 부모 = 4번 노드는 8번 노드에 의해 위로 2개의 노드까지 영향을 미치게 된다.
(현재 노드 기준으로 auth를 감소하며 부모의 alarmCount와 effect를 변경)
→ 8번 노드의 effect[3]는 1 증가
→ 4번 노드의 effect[2]는 1 증가, 4번 노드의 alarmCount는 1 증가,
→ 2번 노드의 effect[1]는 1 증가, 2번 노드의 alarmCount는 1 증가.
7번 노드의 auth는 1이므로, 7번 노드의 effect[1] = 1이 되고, 4번 노드의 alarmCount만 1 증가시킨다.
즉, 7번 노드의 auth는 4번 노드 위의 채팅방에 영향을 끼치지 않는다.
코드로 구현하면 다음과 같다.
auth를 감소하며 parent가 0이거나 auth가 0이 될 때까지 노드의 alarmCount와 effect도 갱신한다.
void initAlarmSetting(int index, int auth)
{
int parent = tree[index].parent;
if (parent == 0 || auth == 0) return;
tree[index].effect[auth]++;
tree[parent].alarmCount++;
auth--;
initAlarmSetting(parent, auth);
}
위 작업을 모든 노드에 대해 실행한다.
for (int i = 1; i <= N; i++) initAlarmSetting(i, tree[i].auth);알림망 설정 ON / OFF
알림이 ON이면 OFF를, OFF면 ON을 시행한다.
그리고 알림이 OFF가 되는 경우라면, 해당 채팅방의 모든 부모의 채팅방 수가 감소(-1) 대상이 된다.
반대로, 알림이 ON이 된다면, 모든 부모의 채팅방 수가 증가(+1) 대상이 된다.
void alarmToggle(int c)
{
int status = tree[c].alarm;
if (status == ALARM_ON)
{
tree[c].alarm = ALARM_OFF;
update(c, c, 1, -1);
}
else
{
tree[c].alarm = ALARM_ON;
update(c, c, 1, +1);
}
}
부모 노드의 update 원리는 다음과 같다.
8번 노드 아래에 자식 노드가 더 있다고 가정하고,
8번 노드의 effect[1] ~ effect[5]가 각각 [5, 3, 1, 4, 7]이라고 하자.
이때, 8번 방의 알람이 꺼지면,
→ 8번의 부모인 4번 방의 알람은 5 + 3 + 1 + 4 + 7 만큼 감소해야 한다. (effect 1 ~ 5)
ㄴ 4번 방의 effect 1 ~ 4는 각각 3, 1, 4, 7 만큼 감소한다.
→ 8번의 부모의 부모인 2번 방의 알람은 3 + 1 + 4 + 7 만큼 감소해야 한다. (effect 2 ~ 5)
ㄴ 2번 방의 effect 1 ~ 3는 각각 1, 4, 7 만큼 감소한다.
→ 8번 부모의 부모의 부모(0번 방이 아니라면...)방의 알람은 1 + 4 + 7 만큼 감소해야 한다. (effect 3 ~ 5)
ㄴ ... effect 1 ~ 2는 4, 7 만큼 감소한다.
→ 위 내용을 노드의 모든 depth (최대 20)에 대해 작업을 하면 된다.
→ 알림이 켜지는 경우는 증가하도록 구현한다.
부모를 찾아가며 갱신하되, 알람이 OFF인 방부터 더 이상 갱신하지 않는다.
코드로 구현하면 다음과 같다.
void update(int index, int target, int depth, int value)
{
int parent = tree[target].parent;
if (parent == 0) return; // 부모가 0인 경우 종료
// 부모의 알람 갱신
for (int i = depth; i <= 20; i++)
tree[parent].alarmCount += (tree[index].effect[i] * value);
// 부모의 effect 갱신
for (int i = depth + 1; i <= 20; i++)
tree[parent].effect[i - depth] += (tree[index].effect[i] * value);
// 알람이 OFF인 경우는 더 이상 update 하지 않음.
if (tree[parent].alarm == ALARM_OFF) return;
// index를 기준으로 parent 및 depth를 증가
update(index, parent, depth + 1, value);
}
value가 +1인 경우 알림을 증가하고, -1인 경우 감소한다.
권한 세기 변경
원래 권한의 세기에 해당되는 effect를 감소하고, 영향이 가는 범위의 부모도 모두 갱신한다.
그리고 다시 새로운 권한만큼 증가시키면 된다.
void setAuth(int c, int power)
{
int auth = tree[c].auth;
int newAuth = power > 20 ? 20 : power;
tree[c].auth = newAuth;
tree[c].effect[auth]--;
updatePower(c, auth, -1);
tree[c].effect[newAuth]++;
updatePower(c, newAuth, 1);
}
updatePower는 다음과 같다.
ALARM이 OFF인 경우, auth가 도달하지 않는 노드(= 0), parent가 0인 경우는 더 이상 업데이트하지 않는다.
void updatePower(int index, int auth, int value)
{
int parent = tree[index].parent;
if (tree[index].alarm == ALARM_OFF || auth == 0 || parent == 0) return;
tree[parent].alarmCount += value;
if (auth > 1) tree[parent].effect[auth - 1] += value;
updatePower(parent, auth - 1, value);
}부모 채팅방 교환
채팅방을 교환하기 위해서는 (켜져 있는) 채팅방을 먼저 끈다.
그러면 채팅방을 교환하더라도 전체 알람에 영향이 없다.
그리고 노드의 부모를 교환한 후, 원래 꺼졌던 채팅방을 다시 켜면 된다.
void change(int c1, int c2)
{
bool status1 = tree[c1].alarm;
bool status2 = tree[c2].alarm;
if (status1 == ALARM_ON) alarmToggle(c1);
if (status2 == ALARM_ON) alarmToggle(c2);
int tmp = tree[c1].parent;
tree[c1].parent = tree[c2].parent;
tree[c2].parent = tmp;
if (status1 == ALARM_ON) alarmToggle(c1);
if (status2 == ALARM_ON) alarmToggle(c2);
}알림을 받을 수 있는 채팅방 수 조회
지금까지 구현된 내용으로 채팅방 수는 즉시 출력이 가능하다.
void retrieve(int c)
{
printf("%d\n", tree[c].alarmCount);
}전체 코드는 다음과 같다.
#include <stdio.h>
#define MAX (100000 + 5000)
#define DEPTH (20 + 3)
#define READY (100)
#define ALARM_ON_OFF (200)
#define SET_AUTH (300)
#define CHANGE (400)
#define RETRIEVE (500)
#define ALARM_OFF (0)
#define ALARM_ON (1)
int N;
typedef struct st
{
int parent;
int auth;
int alarm;
int alarmCount;
int effect[DEPTH];
}NODE;
NODE tree[MAX];
void initAlarmSetting(int index, int auth)
{
int parent = tree[index].parent;
if (parent == 0 || auth == 0) return;
tree[index].effect[auth]++;
tree[parent].alarmCount++;
auth--;
initAlarmSetting(parent, auth);
}
void input()
{
for (int i = 0; i <= N; i++)
{
tree[i].alarm = ALARM_ON;
tree[i].alarmCount = 0;
}
for (int i = 1; i <= N; i++) scanf("%d", &tree[i].parent);
for (int i = 1; i <= N; i++)
{
int auth;
scanf("%d", &auth);
if (auth > 20) auth = 20;
tree[i].auth = auth;
}
for (int i = 1; i <= N; i++) initAlarmSetting(i, tree[i].auth);
}
void printNode(int index)
{
NODE n = tree[index];
printf("=============================\n");
printf("index %d\n", index);
printf("parent : %d\n", n.parent);
printf("auth : %d / alarm %d / alarmCount %d\n", n.auth, n.alarm, n.alarmCount);
printf("effect : ");
for (int i = 0; i < DEPTH; i++) printf("%d ", n.effect[i]);
putchar('\n');
}
void printAllNode()
{
for (int i = 0; i <= N; i++) printNode(i);
putchar('\n');
}
void update(int index, int target, int depth, int value)
{
int parent = tree[target].parent;
if (parent == 0) return; // 부모가 0인 경우 종료
// 부모의 알람 갱신
for (int i = depth; i <= 20; i++)
tree[parent].alarmCount += (tree[index].effect[i] * value);
// 부모의 effect 갱신
for (int i = depth + 1; i <= 20; i++)
tree[parent].effect[i - depth] += (tree[index].effect[i] * value);
// 알람이 OFF인 경우는 더 이상 update 하지 않음.
if (tree[parent].alarm == ALARM_OFF) return;
// index를 기준으로 parent 및 depth를 증가
update(index, parent, depth + 1, value);
}
void alarmToggle(int c)
{
int status = tree[c].alarm;
if (status == ALARM_ON)
{
tree[c].alarm = ALARM_OFF;
update(c, c, 1, -1);
}
else
{
tree[c].alarm = ALARM_ON;
update(c, c, 1, +1);
}
}
void updatePower(int index, int auth, int value)
{
int parent = tree[index].parent;
if (tree[index].alarm == ALARM_OFF || auth == 0 || parent == 0) return;
tree[parent].alarmCount += value;
if (auth > 1) tree[parent].effect[auth - 1] += value;
updatePower(parent, auth - 1, value);
}
void setAuth(int c, int power)
{
int auth = tree[c].auth;
int newAuth = power > 20 ? 20 : power;
tree[c].auth = newAuth;
tree[c].effect[auth]--;
updatePower(c, auth, -1);
tree[c].effect[newAuth]++;
updatePower(c, newAuth, 1);
}
void change(int c1, int c2)
{
bool status1 = tree[c1].alarm;
bool status2 = tree[c2].alarm;
if (status1 == ALARM_ON) alarmToggle(c1);
if (status2 == ALARM_ON) alarmToggle(c2);
int tmp = tree[c1].parent;
tree[c1].parent = tree[c2].parent;
tree[c2].parent = tmp;
if (status1 == ALARM_ON) alarmToggle(c1);
if (status2 == ALARM_ON) alarmToggle(c2);
}
void retrieve(int c)
{
printf("%d\n", tree[c].alarmCount);
}
int main()
{
int Q;
scanf("%d %d", &N, &Q);
for (int q = 0; q < Q; q++)
{
int COMMAND;
scanf("%d", &COMMAND);
if (COMMAND == READY) input();
else if (COMMAND == ALARM_ON_OFF)
{
int c;
scanf("%d", &c);
alarmToggle(c);
}
else if (COMMAND == SET_AUTH)
{
int c, power;
scanf("%d %d", &c, &power);
setAuth(c, power);
}
else if (COMMAND == CHANGE)
{
int c1, c2;
scanf("%d %d", &c1, &c2);
change(c1, c2);
}
else if (COMMAND == RETRIEVE)
{
int c;
scanf("%d", &c);
retrieve(c);
}
}
return 0;
}