<aside> 👉🏿 문제 링크

</aside>

문제 정리

<aside> 👉🏿 n개의 배열을 가진 이진트리가 있다.

리프노드 번호 a, b가 주어진다.

a,b가 이진 트리에서 몇번째 Depth에서 형제 노드가 되는지 구하라.

</aside>

예제로 정리

<aside> 👉🏿 1번 ~ 8번 리프노드에서 4번과 7번이 언제 만나가될까?

</aside>

input = n=8, a=4, b=7
output = 3

접근 방법

<aside> 👉🏿 이진 트리이기 때문에 항상 2n개의 리프 노드가 주어졌을 것이다.

따라서 중간 값을 지정해준다.

중간값을 기준으로 좌 우로 나뉜 경우 현재 depth를 반환해준다.

중간값을 기준으로 a, b 모두 한쪽에 몰려있다면 mid를 줄이거나 늘려나간다.

</aside>

코드로 정리

• 전체코드

<aside> 👉🏿 최대 depth를 지정해준다.

a는 작은 값, b는 큰 값으로 지정해준다.

중간값은 전체 크기 //2 로 지정해준다.

리프노드에서 lower과 upper 즉, 하한과 상한을 지정한다.

</aside>

max_round = math.log2(n)        # 최대 depth 지정
a, b = min(a, b), max(a, b)     # a = 작은 값, b = 큰 값
mid = n // 2                    # 중간값
lower = 0                       # 최소값
upper = n                       # 최대값

<aside> 👉🏿 반복문을 시작한다. 종료조건은 아래와 같다.

a, b가 중간값을 기준으로 분리되어있을 경우에 종료시킨다.

</aside>