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

이번 문제는 완전탐색에 대한 문제입니다.

 

일단 포화 이진 트리로 만들고, 탐색을 시작합니다.

루트노드부터 시작해서 제일 왼쪽 리프노트의 부모노드까지 내려옵니다. 이 서브트리가 올바른 트리인 지 확인합니다. 

 

어려운 점은 자식노드나 부모노드 간의 이동이 어려웠습니다.

 

from collections import deque
import itertools
import math

flag = True

def solution(numbers):
    answer = []
    
    for i in numbers:
        if i == 1:
            answer.append(1)
        else:
            an = ans(dec_to_bin(i))
            if an == -1:
                an =0
            answer.append(an)
    
    return answer


def dec_to_bin(number):
    ret = deque()
    while number!= 1:
        ret.appendleft(number%2)
        number = number // 2
        
    ret.appendleft(1)
    
    n = int(math.log2(len(ret))) + 1
    
    while 2**n-1 != len(ret):
        ret.appendleft(0)

    
    return ret

def ans(number):
    n = int(math.log2(len(number)))
    mid = len(number)//2

    return search(mid, number, n)


def search(idx, number, level):
    if (idx+1)%2 == 1:
        return number[idx]
    
    left = idx - 2**(level-1)
    right = idx + 2**(level-1)
    
    
    l = search(left, number, level-1)
    r = search(right, number, level-1)
    
    if l == -1 or r == -1:
        return -1

    if number[idx] == 0:
        if l == 0 and r == 0:
            return 0
        else:
             return -1

    else:
        return  1