[26주차_월요일] 코드트리 메신저

[KodaHye]

• 사이트: 코드트리(CT)
• 문제: 코드트리 메신저
• 년도: 2023

### 🤔 시간복잡도 고려사항



### 💡 풀이 아이디어

[jmxx219]

🤔 시간복잡도 고려사항

• 1 ≤ Q(명령 수) ≤ 100,000, 1 ≤ N(채팅방 수) ≤ 100,000, 1 ≤ 이진트리 최대 깊이 ≤ 20
• 단순 DFS 탐색 -> 모든 명령마다 이진트리 탐색을 진행할 경우 O(QN) -> 시간 초과 발생
• 이진 트리 깊이가 최대 20인 것을 활용하기

💡 풀이 아이디어

• 이진 트리 만들기

  static class Room {
  	int c;
  	boolean alert;
  	int authority;
  
  	int parent;
  	int leftChild;
  	int rightChild;
  
  	int[] effect;
  
  	public Room(int c) {
  		this.c = c;
  		this.alert = true;
  		this.parent = -1;
  		this.leftChild = -1;
  		this.rightChild = -1;
  		this.effect = new int[DEPTH + 1];
  	}
  
  	public void toggleAlert() {
  		this.alert = !this.alert;
  	}
  }

  • int[]effect : 노드별로 상위 노드로 전달할 수 있는 알람 수를 저장한다.

0. 변경된 상황 반영

   private static void update(int c) {
   	while (c != 0) {
   		Room curr = rooms[c];
   		Arrays.fill(curr.effect, 0);
   		for (int i = 0; i <= curr.authority; i++) {
   			rooms[c].effect[i]++;
   		}
   
   		if(curr.leftChild != -1 && rooms[curr.leftChild].alert) {
   			for (int i = 1; i <= DEPTH; i++) {
   				curr.effect[i - 1] += rooms[curr.leftChild].effect[i];
   			}
   		}
   
   		if(curr.rightChild != -1 && rooms[curr.rightChild].alert) {
   			for (int i = 1; i <= DEPTH; i++) {
   				curr.effect[i - 1] += rooms[curr.rightChild].effect[i];
   			}
   		}
   
   		c = rooms[c].parent;
   	}
   }

   • 변경이 발생한 인덱스부터 계산을 다시 시작하여 상위 노드로 거슬러 올라가는데, 이때 자식의 알람 기능이 켜져있어야만 결과 반영하기
   • 현재 인덱스에서 왼쪽과 오른쪽 자식 노드가 보낼 수 있는 알람 수 만큼 함께 더해준다. 그러면 현재 인덱스에서 자식 노드까지 포함하여 상위 노드로 보낼 수 있는 알람 수가 반영된다.

1. 사내 메신저 준비(이진 트리 초기화)

   private static void init(StringTokenizer st) {
   	rooms = new Room[N + 1];
   	for (int i = 0; i <= N; i++) {
   		rooms[i] = new Room(i);
   	}
   
   	for (int i = 1; i <= N; i++) {
   		int pIdx = Integer.parseInt(st.nextToken());
   		rooms[i].parent = pIdx;
   		if(rooms[pIdx].leftChild == -1) rooms[pIdx].leftChild = i;
   		else rooms[pIdx].rightChild = i;
   	}
   
   	for (int i = 1; i <= N; i++) {
   		rooms[i].authority = Integer.parseInt(st.nextToken());
   		if(rooms[i].authority > DEPTH) rooms[i].authority = DEPTH;
   	}
   
   	initEffect(0);
   }

   private static void initEffect(int c) {
   	if(c == -1) return;
   
   	Room curr = rooms[c];
   	for (int i = 0; i <= curr.authority; i++) {
   		rooms[c].effect[i]++;
   	}
   
   	initEffect(curr.leftChild);
   	initEffect(curr.rightChild);
   
   	if(curr.leftChild != -1) {
   		for (int i = 1; i <= DEPTH; i++) {
   			curr.effect[i - 1] += rooms[curr.leftChild].effect[i];
   		}
   	}
   
   	if(curr.rightChild != -1) {
   		for (int i = 1; i <= DEPTH; i++) {
   			curr.effect[i - 1] += rooms[curr.rightChild].effect[i];
   		}
   	}
   }

2. 알림망 설정

   private static void toggleNotification(int c) {
   	rooms[c].toggleAlert();
   	update(c);
   }

3. 권한 세기 변경

   private static void changeAuthority(int c, int power) {
   	rooms[c].authority = power > DEPTH ? DEPTH : power;
   	update(c);
   }

4. 부모 채팅방 교환

   private static void swapParent(int c1, int c2) {
   	int p1 = rooms[c1].parent;
   	int p2 = rooms[c2].parent;
   
   	if(rooms[p1].leftChild == c1) {
   		rooms[p1].leftChild = c2;
   	} else if(rooms[p1].rightChild == c1) {
   		rooms[p1].rightChild = c2;
   	}
   
   	if(rooms[p2].leftChild == c2) {
   		rooms[p2].leftChild = c1;
   	} else if(rooms[p2].rightChild == c2) {
   		rooms[p2].rightChild = c1;
   	}
   
   	rooms[c1].parent = p2;
   	rooms[c2].parent = p1;
   
   	update(c1);
   	update(c2);
   }

5. 알림 받을 수 있는 채팅방 수 조회

   • rooms[c].effect[0] - 1

다른 사람 풀이 참고했습니다.. 거의 복붙입니다..

[KodaHye]

https://kdhdh09.tistory.com/43

혼자서 안풀려서, 풀이 해설 식으로 공부했습니다,,,, 😭
내용이 많아서 블로그에 글 썼습니다,,