[프로그래머스]Lv3. 표현 가능한 이진트리(Python)

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

프로그래머스

 

문제 이해 

 

처음에 문제 이해에 다소 어려움을 겪었지만 이진트리를 그려보고 중위순회(L->루트->R)로 노드가 존재하면 1 존재하지 않으면 0 이렇게 읽은 후 이진수로 나열한 후 십진수로 변환하면 해당 숫자를 알아낼 수 있다. 

 

만약 이진트리로 해당 숫자를 나타낼 수 있으면 1을 리턴, 그렇지 않으면 0을 리턴 

 

7 => 111

42 => 0101010

 

3 => 11 => 011 (O)

5 => 101 (X)

 

1. 주어진 수를 이진수로 변환하자

파이썬에서 제공하는 bin 함수를 사용해 변환해보자

import math

num = int(input())

# 입력된 숫자를 2진수로 변환, [2:]를 사용하여 '0b'를 제외
bin_num = bin(num)[2:]

# 이진포화트리는 2^n - 1의 자릿수
digit = 2 ** (int(math.log(len(bin_num), 2)) + 1) - 1  

# digit에서 num_bin의 길이를 뺀 만큼 '0'을 반복하여 앞에 추가하고, 그 뒤에 이전에 계산한 2진수를 붙임 
bin_num = "0" * (digit - len(bin_num)) + bin_num

 

코드

import math
def check(num_bin, prev_parent):
    # 중앙값(자손) 기준으로 재귀적으로 확인
    mid = len(num_bin) // 2
    if num_bin: son = (num_bin[mid] == '1')
    else: return True
    
    # 내가 존재하면 부모가 존재해야함.
    if son and not prev_parent:
        return False
    else:
        return check(num_bin[mid + 1:], son) and check(num_bin[:mid], son)

def sol(num):
    # 1은 항상 참
    if num == 1: return 1

    # 2진수 변환
    num_bin = bin(num)[2:]
    # 2^n - 1꼴의 자릿수를 가져야함.
    digit = 2 ** (int(math.log(len(num_bin), 2)) + 1) - 1
    num_bin = "0" * (digit - len(num_bin)) + num_bin
    # print(digit, num_bin)
    
    # 누군가의 부모 노드는 항상 존재해야함. 
    if num_bin[len(num_bin) // 2] == '1'and check(num_bin, True): return 1
    else: return 0

def solution(numbers):
    answer = []
    for num in numbers:
        answer.append(sol(num))
    return answer