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

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

프로그래머스

 

---

• 풀이
  • 이진트리를 수로 표현
    1. 10진수를 2진수로 만들기 : bin(num)[2:]
    2. 포화 이진 트리로 만들기
       • 포화 이진 트리 노드 개수 == (2**n)-1
       • n 을 구해야 함 (아래 표 보기)
         • n = 정수(log2(길이)) + 1
         • n == (int(math.log(len(num), 2)) + 1)
       • 2진수에서 왼쪽에 모자란 길이만큼 0 추가
    3. 포화 이진 트리가 가능한 형태인지 확인
       • 부모가 없이 자식만 존재하는 경우 찾기
       • 포화 이진 트리 에서 루트 노드는 가장 중간에 있다!!!

현재 이진수의 길이	목표 : (2^n)-1	n	log2(길이)
1	1	1	0
2	3	2	1
3	3	2	1.xx
4	7	3	2.xx
5	7	3	2.xx
6	7	3	2.xx
7	7	3	2.xx
8	15	4	3.xx
9	15	4	3.xx

 

 

• 코드

import math

# 3. 
# 자식과 부모 확인
# parent : 부모 존재 여부
def child_parent(num,parent):
    if num == '':
        return True
    mid = len(num)//2
    me = num[mid]
    # 내가 1인데 부모가 0이면
    if me == '1' and parent =='0':
        return False
    else:
        # 나의 자식 확인
        return child_parent(num[:mid],me) and child_parent(num[mid+1:],me)

# 2. 표현 가능한가?
def check(num):
    if num == 1:
        return 1
    # 2진수로 바꾸기
    num = bin(num)[2:]
    # 포화 이진 트리로 만들기 -> len(num)을 2**n-1로 만들기
    digit = 2 ** (int(math.log(len(num), 2)) + 1) - 1
    # 0추가
    num = "0" * (digit - len(num)) + num
    
    # 자식 중 1이 있다면 부모 노드는 항상 1이어야 한다.
    if num[len(num)//2] == '1' and child_parent(num,True):
        return 1
    else:
        return 0

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