문제
- update 과정은 가급적 O(depth)로 처리!
- 런타임 에러 조심할 것!
구현할 API 설명
void init()
- 최초 1회 실행
- 0번 root 노드는 주어지지 않음
- 알람은 부모로 전파 됨
Q : [1, 100000] // 쿼리 수
N : [1, 100000] // 0번 제외 노드 수
D : [1, 20] // 이진 트리 최대 깊이, depth
pi : [0, N] // 부모 노드 번호
ai : [1, N] // 권한 세기void updateAlarm(int c)
- c번 노드 알람 전파 ON/OFF toggle
c : [1, N]void updateAuth(int c, int power)
- c번 노드 권한 세기 변경
c : [1, N]
power : [1, N]void updateParents(int c1, int c2)
- c1번 노드, c2번 노드 부모 변경
- c1번 노드와 c2번 노드는 동일한 depth
c1, c2 : [1, N]int get(int c)
- c번 노드에 알림을 보낼 수 있는 하위 채팅방(노드) 개수(본인은 제외)
c : [1, N]풀이
권한 설정
전파 거리 관리
어떻게 전파 거리를 고려하여 값을 가지고 있는가에 대한 고민을 하면 됩니다. 사실 가장 기초적인 방법으로는 Node 구현 시 List<Node> 형태로 해당 노드로 전파 가능한 하위 노드들을 들고 있으면 되긴 합니다.
하지만 삽입 삭제 과정이 빈번하게 일어나는 상황에서 이는 바람직하지 않습니다. 어떤 방법을 쓰면 될까요?
이 때 우리는 조건 D <= 20 이 수상합니다. 이걸 활용해서 가능합니다.
어차피 우리에게 필요한 건 하위 노드의 종류가 아닌 전파 거리만이 필요합니다. 그래서 이를 관리해주는 카운팅 배열 cnt[D] 를 만들어 줍니다.
cnt[i] : 전파 거리가 i 만큼 남은 하위 노드의 개수
ex) 0 - 1(auth = 1) - 2(auth = 1) - 3(auth = 2) 와 같은 트리에서
3 - cnt : [0, 0, 0, 0, ...]
2 - cnt : [0, 1, 0, 0, ...] // 노드 3의 전파 거리 2 - 1
1 - cnt : [2, 0, 0, 0, ...] // 노드 2의 전파 거리 1 - 1, 노드 3의 전파 거리 2 - 1 - 1
0 - cnt : [1, 0, 0, 0, ...] // 음수가 되면 사라짐, 노드 1의 전파 거리 1 - 1그리고 update나 get을 할 때 이 배열 전체를 순회하면 됩니다. 배열의 사이즈는 D 로 잡으면 충분합니다. 어차피 제일 깊은 곳에서 root 까지 올라와도 겨우 20회 확인하기 때문입니다.
setValue & setSub
각각의 역할은 다음과 같습니다.
setValue: 전파 거리 딱 하나 바뀌었을 때 update 수행setSub: 서브 트리 자체가 바뀌었을 때 update 수행
setValue(int id, int val, int power)
- id번 노드의 auth 값이 power 로 변경이 될 때 val 만큼 cnt를 변경해주는 update
- 단일 값이 수정 될 경우 사용하고, root거나 전파 거리가 부족하거나 알람 OFF라면 break
- 자식에서 부모로 이동하는 것이 핵심 포인트!
O(D)
static void setValue(int id, int val, int power) {
while(true) {
if(parents[id] == -1 || power-- == 0 || alarm[id] == -1) break;
node[parents[id]].cnt[power] += val;
id = parents[id];
}
}setSub(int id, int val)
- id번 노드를 root로 하는 서브트리를 그 부모 노드에 할당 또는 제거하는 연산
- 알람 ON/OFF, parents 바꾸기 등에 사용
setValue를 root(id번 노드) 의 auth를 한번 적용한 것과 cnt의 크기(D) 만큼 수행O(D^2)
static void setSub(int id, int val) {
setValue(id, val, node[id].auth);
for(int power = 1; power < 20; power++) {
setValue(id, val * node[id].cnt[power], power);
}
}추가 메소드의 사용처
setValue:updateAuth-O(D)setSub:updateAlarm,updateParents-O(D^2)
주의 사항
권한 세기
- 권한 세기를 정할 때 p 가 D 보다도 크게 나오는 경우가 존재 - 런타임 에러
- setter 를 통해서 값을 변경하도록 함 - 캡슐화 필요
static class Node {
int id, auth;
int[] cnt;
public Node(int id, int auth) {
this.id = id;
setAuth(auth);
cnt = new int[20];
}
public void setAuth(int auth) { // setter를 만들어 두기
this.auth = auth > 20 ? 20 : auth;
}
@Override
public String toString() {
return "Node [id=" + id + ", auth=" + auth + ", cnt=" + Arrays.toString(cnt) + "]";
}
}- 값을 바꿀 때는 setter를 거칩니다.
static void updateAuth(int c, int power) {
setValue(c, -1, node[c].auth);
node[c].setAuth(power); // setter를 통한 값 변경
setValue(c, 1, node[c].auth);
}알람 ON/OFF
setSub도 사용하는setValue를 보면 알겠지만 알람 OFF의 경우에는 update X- 알람 ON :
alarm[i] == 1, 알람 OFF :alarm[i] == -1
- 알람 ON :
- 알람의 초기 상태에 따라 동작 과정이 다름
- 알람 ON → OFF
setSub(id, -1): 상위 노드 cnt 하나씩 빼주기alarm[id] = -1: 알람 OFF
- 알람 OFF → ON
alarm[id] = 1: 알람 ONsetSub(id, 1): 상위 노드 cnt 하나씩 더해주기
- 알람 ON → OFF
시간 복잡도
API 별
init:O(D * N)updateAlarm:O(D^2)updateAuth:O(D)updateParents:O(D^2)get:O(D)
전체
O(D^2 * Q + D * N)
코드
import java.io.*;
import java.util.*;
public class Main {
static class Node {
int id, auth;
int[] cnt;
public Node(int id, int auth) {
this.id = id;
setAuth(auth);
cnt = new int[20];
}
public void setAuth(int auth) {
this.auth = auth > 20 ? 20 : auth;
}
@Override
public String toString() {
return "Node [id=" + id + ", auth=" + auth + ", cnt=" + Arrays.toString(cnt) + "]";
}
}
static int N, Q;
static int[] parents, auth, alarm;
static Node[] node;
static void init() {
parents[0] = -1;
node = new Node[N + 1];
alarm = new int[N + 1];
Arrays.fill(alarm, 1);
for(int i = 0; i <= N; i++) {
node[i] = new Node(i, auth[i]);
}
for(int i = 0; i <= N; i++) {
setValue(i, 1, node[i].auth);
}
}
static void setValue(int id, int val, int power) {
while(true) {
if(parents[id] == -1 || power-- == 0 || alarm[id] == -1) break;
node[parents[id]].cnt[power] += val;
id = parents[id];
}
}
static void setSub(int id, int val) {
setValue(id, val, node[id].auth);
for(int power = 1; power < 20; power++) {
setValue(id, val * node[id].cnt[power], power);
}
}
static void updateAlarm(int c) {
if(alarm[c] == -1) {
alarm[c] = 1; setSub(c, 1);
} else {
setSub(c, -1); alarm[c] = -1;
}
}
static void updateAuth(int c, int power) {
setValue(c, -1, node[c].auth);
node[c].setAuth(power);
setValue(c, 1, node[c].auth);
}
static void updateParents(int c1, int c2) {
setSub(c1, -1); setSub(c2, -1);
int p1 = parents[c1], p2 = parents[c2];
parents[c1] = p2; parents[c2] = p1;
setSub(c1, 1); setSub(c2, 1);
}
static int get(int c) {
int ans = 0;
int[] cnt = node[c].cnt;
for(int i : cnt) {
ans += i;
}
return ans;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
parents = new int[N + 1];
auth = new int[N + 1];
StringBuilder sb = new StringBuilder();
for(int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine());
int query = Integer.parseInt(st.nextToken());
int c, c1, c2, power;
switch(query) {
case 100:
for(int j = 1; j <= N; j++) parents[j] = Integer.parseInt(st.nextToken());
for(int j = 1; j <= N; j++) auth[j] = Integer.parseInt(st.nextToken());
init();
break;
case 200:
c = Integer.parseInt(st.nextToken());
updateAlarm(c);
break;
case 300:
c = Integer.parseInt(st.nextToken());
power = Integer.parseInt(st.nextToken());
updateAuth(c, power);
break;
case 400:
c1 = Integer.parseInt(st.nextToken());
c2 = Integer.parseInt(st.nextToken());
updateParents(c1, c2);
break;
case 500:
c = Integer.parseInt(st.nextToken());
sb.append(get(c)).append('\n');
break;
}
}
System.out.print(sb);
br.close();
}
}
언제나 탐구하고 공부하는 개발자, 주재완입니다.