[파이썬] 카카오 2023 - 표현 가능한 이진트리

처음에 풀지 못했다. 포화 이진 트리의 개념을 정확히 알고 난 후에 단서를 찾았다. 사실 문제를 정확히 읽지 않았기 때문에 이 부분을 놓친 것 같다. 이 단서가 없다면 풀 수 없다.
포화 이진 트리에서는 늘 정 가운데가 root가 되고 좌우를 반씩 나눈 후에 다시 가운데를 subtree root로 보고 이진분할, 이진탐색을 할 수 있다.

핵심 요소

1. mid를 먼저 찾고 진행한다.
2. 종료 조건은 (base case) 더 이상 분할 할 수 없는 단위(1개)에 도착했을 때(True) 와 중앙 값인 root가 존재하지 않는 상황(bi[mid]==0)에서 좌우측 child가 존재하는 경우이다. 좌우측 child를 찾는 방식도 역시 좌우측의 중앙값을 찾는 것과 같다.
3. 해당하지 않으면 계속 진행하는데 좌우측이 동시에 True인 경우만 진정으로 True이기 때문에 return에는 좌우 두 조건을 모두 사용했다.

기타 요소

이 부분은 이진 변환을 하였을 때 앞 자리에 0이 표현되지 않기 때문에 필요하다. 포화 이진 트리의 경우 항상 2**n-1 개의 노드가 존재해야 하는데, 이진변환을 했을 때 이 수보다 작다면 이 숫자만큼 앞자리의 0을 더해주는 변환이 필요하다.

끝.

def binary_search(start, end, bi)->bool:
    mid = (start + end) //2
    if start == end-1:
        return True
    if not bi[mid] and (bi[(start+mid)//2]==1 or bi[(mid+1+end)//2]==1):
        return False

    return binary_search(start, mid, bi) and binary_search(mid+1,end, bi)

import sys
sys.setrecursionlimit(1000000)
def binary_search(start, end, bi)->bool:
    mid = (start + end) //2
    # flag가 있는 상태에서 root node 좌우로 1이 있는 경우
    if start == end-1:
        return True
    if not bi[mid] and (bi[(start+mid)//2]==1 or bi[(mid+1+end)//2]==1):
        return False
    # 끝까지 도달  한 경우 node val은 0 또는 1이며 False를 반환한 적이 없으므로 문제가 없다.

    return binary_search(start, mid, bi) and binary_search(mid+1,end, bi)


def solution(numbers):
    answer = []
    for num in numbers:
        bi = bin(num).split('b')[-1]
        n = 0
        while len(bi) >= 2**n:
            n+=1
        # numbers to add prefix
        for _ in range(2**n-1 - len(bi)):
            bi = '0'+bi
        bi = [*map(int,list(bi))]
        answer.append(binary_search(0,2**n-1, bi))
    return [*map(int,answer)]