프로그래머스 lv3 표현가능한이진트리

1. 개요

• https://school.programmers.co.kr/learn/courses/30/lessons/150367

2. 풀이

import math

def solution(numbers):
    return [Solution(n) for n in numbers]

def Solution(number):
    number = format(number, "b")
    
    # 포화이진트를 만족하는 길이가 될때까지(2^n-1) 수의 앞에 0을 붙인다.
    while int(math.log(len(number)+1,2)) != math.log(len(number)+1,2):
        number = "0"+number

    return representAble(number, 0, len(number)-1)[0]

def representAble(number, left, right):
    if left==right:
        return (1, number[left])
    
    mid = (left+right) // 2
    
    leftResult, leftV = representAble(number, left, mid-1)
    rightResult, rightV = representAble(number, mid+1, right)
    
    
    if not leftResult or not rightResult:
        return (0, -1)
    # 루트가 0인데 자식이 1이라면 표현가능한 이진트리가 아니라 그래프가 된다.
    elif number[mid]=="0" and (leftV=="1" or rightV=="1"):
        return (0, -1)
    else:
        return (1, number[mid])