[programmers/Lv.3] 표현 가능한 이진트리

❓  문제

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

 

🛎️  풀이 과정

두 가지의 과정이 필요하다.

1. 포화 이진 트리 만들기
2. 부모, 자식 관계 재귀적으로 확인하기

포화 이진트리를 만들기 위해서는 2^n - 1꼴의 자릿수를 가져야한다.
그리고 확인할 리스트(num)와 해당 리스트의 부모(parent)를 재귀적으로 확인한다.
해당 리스트의 가장 탑노드(child)는 파라미터로 보낸 부모(parent)의 자식이다.
따라서 왼쪽, 오른쪽의 child를 확인해서 parent와 비교한다.

두 가지의 과정이 필요하다는 것까지 확인했지만,
구현에 어려움을 느껴 블로그를 참고하였다.

 

💻  풀이

import math

def is_tree(num, parent):
  if num:
    mid = len(num) // 2
    # 자식이 있는지 없는지 확인
    child = num[mid] == "1"
  else:
    return 1

  if child and not parent:
    return 0
  else:
    return is_tree(num[:mid], child) and is_tree(num[mid+1:], child)

def check(num):
  if num == 1: return 1

  # 2진수 변환
  b_num = bin(num)[2:]

  # 2^n - 1꼴의 자릿수를 가져야함.
  digit = 2 ** (int(math.log(len(b_num), 2)) + 1) - 1
  b_num = "0" * (digit - len(b_num)) + b_num

  # 자식이 있는 부모가 0이 아닌지 확인
  if b_num[len(b_num) // 2] == "0":
    return 0
  else:
    return is_tree(b_num, 1)

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

print(solution([63, 111, 95, 1, 0]))