코드트리 메신저

문제 링크

코드트리 메신저 풀기

난이도

플래티넘4
- 시간초과의 늪
- 자료구조를 어떻게 구성하는지 중요
- 링크드 리스트로 트리를 만들 줄 알아야 한다.

문제요약

이진트리 형태의 알림망 존재
- 각 노드는 채팅방
알림은 자식이 되는 아래에서 부터 시작해 위로 전달된다.
각 채팅방마다 세기가 존재
- 3이면 부모 3명까지 전달된다.
전체 5개의 함수를 구현해야 한다.
- 사내 메신저 준비
  - N개의 채팅방의 부모채팅방 번호 입력
  - N개의 채팅방의 세기 입력
  - 0번은 root노드
- 알림망 설정onoff
  - 해당 채팅방의 부모로의 연결을 끊어버린다.
- 권한세기 변경
  - 해당 채팅방의 세기를 수정한다.
- 부모 채팅방 교환
  - 서로 같은 높이의 채팅방을 교환
  - 해당 채팅방의 자식들도 같이 이동한다
- 알림받는 채팅방 수 조회
  - 해당 채팅방으로 알림이 오는 채팅방을 조회한다.

접근

1. 완전탐색

제일 간단하며 채팅방 수 조회할때 해당 채팅방을 기준으로 자식들을 전부 조회한다.

2. 시간초과가 나는곳을 확인

전체 채팅방은 100,000, 함수 총호출은 100,000
트리로 만들었을때 최대 높이는 20이 된다고 문제에서 정의된다.
제일 시간 오래걸리는 채팅방 수 조회는 미리 계산되서 바로 o(1)로 출력이 되어야 한다.
그러면 나머지 onoff, 세기변경, 부모 교환시 트리높이정도의 계산량이 나와야 시간초과가 안난다는 의미다.

3. 제일 시간초과가 나올곳은?

onoff, 권한세기, 부모교환 다 달라보이지만, 내부적인 로직은 다 유사한거 처럼 보인다. 하지만!
onoff에서의 시간을 빠르게 줄여야한다.
- onoff는 현재자신포함, 모든 자식들의 세기를 확인해서 부모에게 전달해야한다.
- 권한세기는 본인만 부모에게 알리면되므로 최대 20

4. onoff를 줄이기 위한 자료구조

노드마다 부모로가는 세기를 저장하는 구조로 간다!
해당 자료구조는 array로 만들어진다.
- 부모가 최대20개로 고정되어있어서 20개의 array로 만들어도 되고 , list로 해도되고
- index는 현재노드에서 부모까지의 거리가 된다.
  - 0은 바로부모노드, 1은 부모의 부모노드,…
- value는 해당 노드까지로 전달될 채팅방의 갯수이다.
예로 그림을 보면서 확인해보자.

위와 같은 구조로 밑부터 2의 세기, 1의 세기, 1의세기를 가졌다고 보자
- 10번은 11번,12번까지 세기가 전달된다.
- 11번은 12번까지 전달
10번은 11번, 12번까지, 11번은 12번까지 간다는 정보를 어떻게 표현할까

먼저 10번부터 시작해서 설명한다.
- 10번은 11번, 12번꺄지 세기가 전달된다.
- list로 [1,1]형태가 만들어진다.
  - 부모인 10번에 1개의 채팅방이 알림간다는 의미
  - 부모의부모인11번에 1개 채팅방이 알림간다는 의미

다음 11번을 보자
- 바로 자식의 list를 0부터 시작해 조회한다.
- 해당 (자식)list[0]은 본인이 받는 세기가 된다.
- (자식)list[1]부터는 본인 기준 부모에게 전달될 세기가 된다.
- 그리고 본인도 부모인 12번에게 세기가 전달된다.
- 그러면 list는 [1+1]이된다.
  - 자식에게서 올라온 세기1 + 본인이 올리는 세기1
쉽게 생각하자!
- 자식에게 올라오는 list는 index 0번은 내가 받는세기
- index1 부터는 본인의 list0번부터 합친다
- 복잡하네
그림으로 표현하면 이렇게 된다.
마지막 12번은 이렇게 된다.
좀더 큰 트리로 가정해서 더 복잡하게 해본 또다른 예시이다.
11번은 두개의 자식으로 9,10번이 있다고 하자.
- 그밑으로 많은 자식을 가지고 오는 세기도 다양하다.
그러면 11번은 어떻게 될까
일단 자식에게 오는 list의 0번을 더하면 본인이 받는 세기가 된다.
- 그리고 자식에게서 오는 list의 1번부터는 본인의 부모에게 전달되는 세기정보가 된다.
- 10번에게서 온 list는 1번부터 해서 [5,5,2,1]
- 9번에게서 온 list는 1번부터 해서 [3,1]
- 그리고 본인은 세기가 1이므로 [1]
- 이 3개를 더해서 [9,6,2,1]이 11번의 부모로 전달되는 세기 list가 되는것이다.
이런식으로 12번의 list와 받는세기도 결정된다.
이 자료구조는 onoff에서 depth*depth정도만 걸린다.
- off시에 해당 채팅방이 가진 list정보를 부모에게 올라가면서 빼주기만 하면 된다.
- on시에는 해당 채팅방이 가진 list정보를 부모에게 올라가면서 더해주기만 하면 된다.
- 부모노드는 최대 20(depth)이고 list도 최대20(depth)이므로 20*20으로 해결이된다.

간단 알고리즘

채팅방 구성
- 채팅방번호, 세기, 부모노드, onoff여부, 핸재 채팅방에 전달 받는 채팅방 수 cnt
- 부모세기list
  - 위에서 설명한 list로 부모들에게 전달되는 세기들을 저장
  - index는 부모까지의 거리, value는 해당 부모로 전달되는 채팅방 수
트리구성
- array로 만들어 특정 트리노드를 바로 접근이 되게한다.
함수:준비(p[],c[])
- 입력되는 부모 번호와, 파워 세기들을 초기화한다.
  - Node[] trees와 같은 형태로 만들어 관리
- 각 노드마다 부모세기list를 만들고 초기화 진행
  - 최대 깊이는 20이므로 20짜리의 arr로 관리하거나 list로 구성
  - 각 채팅방 부터 시작하여 부모로 이동하면서, 부모세기 list를 갱신한다.
함수:onof(c 노드번호)
- 해당 노드번호의 onoff를 변경한다
- on인 경우
  - 해당 c의 부모세기list를 확인
  - 부모노드로 올라가면서 cnt를 +해준다.
  - 부모노드의 부모세기 list도 c의 부모세기로 부터 +해준다.
  - 이것을 부모노드가 off가 나올때 까지 진행한다.
- off인경우
  - 해당 c의 부모세기 list를 확인
  - 부모노드로 올라가면서 cnt를 -해준다.
  - 부모노드의 부모세기 list도 c의 부모세기로 부터 -해준다.
  - 이것을 부모노드가 off가 나올때 까지 진행한다.
함수:권한세기 변경(c 노드번호, p 새로운 세기)
- 해당 노드의 권한 세기를 변경한다.
- 새로운 세기가 기존보다 큰경우
  - 부모세기 list를 갱신
    - 기존세기가 닿는 위치부터 새로운 세기까지를 +1해준다.
  - 새로운 세기가 처음 닿는 위치인경우
    - cnt를 +1해준다.
- 기존보다 작은 세기인경우
  - 부모세기list를 갱신
    - 새로운 세기부터 기존세기까지 -1를 해준다.
  - 새로운 세기 이후부터의 부모는 cnt를 -1한다.
- 이과정을 off가 나올때까지 진행한다.
함수:부모 채팅방 교환(a 노드번호,b노드번호)
- 두 채팅방의 부모가 같으면 넘긴다.
- 두 채팅방 off진행
- 두 채팅방의 부모를 교환
- 두 채팅방을 on진행
  - 초기에 off였으면 넘긴다.
함수: 알림받는 채팅방 수 조회(c 노드번호)
- 해당 채팅방의 cnt를 출력한다.

후기

구현 자체는 오래 안결렸지만 시간 초과로 오래 고생했다.
시간초과를 해결한 부모세기list 아이디어를 뽑는데 오래걸렸다.
- 이전 아이디어는 각 채팅방 마다 오는 자식들의 세기를 저장했다.
  - 해쉬맵 형태로 key는 채팅방번호, value는 해당 채팅방의 세기이다.
  - 이는 부모노드로 올라가면서 value를-1씩 해주는 방식으로 했다.
- 이 구조도 좋다 생각했고, depth만큼 한다는 착각을 가졋다.
- 실제로는 자식의 갯수*depth만큼으로 자식의 갯수는 당연히 채팅방의 갯수로 시간초과가 나는 이유가 되었다.
이런 구현이전에 설계에서 시간초과가 나는 이유를 알지 못하면 최적화를 어디서 할지, 어떻게 시간을 줄여야 하는지에 대한 선입견이 생겨 수정하기 어려워진다.
초기에 설계시에 잘 생각해야 하는 문제였다.