[프로그래머스 LV 3] 표현 가능한 이진트리 (파이썬/python)

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

프로그래머스

 

 

풀이방법으로는

1. 이진수로 변환한다

2. 변환한 이진수를 포화 이진트리로 만들 수 있게 0 을 붙여줌 ( 2^n - 1 을 충족해야함 )

3. 부모를 탐색하고,  분할정복을 이용해서 좌, 우 를 재귀로 탐색한다.

 

import math


def solution(numbers):
    answer = []

    for number in numbers:
        binary_num = to_binary_num(int(number))
        full_binary_tree_num = to_full_binary_tree_able_num(binary_num)

        answer.append(check_if_binary_tree_is_possible(full_binary_tree_num))

    return answer


# 포화 이진트리가 가능한 사이즈를 만들기위해 앞에다가 0 을 붙여줌.
# 포화 이진트리가 가능하기 위해서는 number 의 사이즈가 2^n - 1 를 정수로 충족해야함.
def to_full_binary_tree_able_num(number):
    number_len = len(number)

    while not float.is_integer(math.log2(number_len + 1)):
        number_len += 1

    return "0" * (number_len - len(number)) + number


# 2진수 변환
def to_binary_num(number):
    binary_num = ""

    while number > 0:
        binary_num = str(number % 2) + binary_num
        number = number // 2

    return binary_num


# 분할정복을 이용해 좌 우 를 각각 탐색해줌
def check_if_binary_tree_is_possible(binary_num):
    # 리프노드는 0이던 1이던 상관없음
    if len(binary_num) == 1:
        return 1

    left = binary_num[0:len(binary_num) // 2]
    right = binary_num[len(binary_num) // 2 + 1:len(binary_num)]

    # 자식 노드가 둘다 0이 아니면 부모 노드가 1 이여야 함
    if binary_num[len(binary_num) // 2] == "0":
        if left[len(left) // 2] != "0" or right[len(right) // 2] != "0":
            return 0

    left_result = check_if_binary_tree_is_possible(left)
    right_result = check_if_binary_tree_is_possible(right)

    if left_result == 1 and right_result == 1:
        return 1

    return 0