[프로그래머스] 150367. 표현 가능한 이진트리 | 시뮬레이션, 구현 | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

• 정수가 주어질 때 2진수로 변환한 값을 이진트리로 표현할 수 있는지 검사하라
• 이진트리를 수로 표현하는 방법은 다음과 같다.
  • 이진트리에 더미노드를 추가해 포화 이진트리로 만든다.
  • 맨 왼쪽 노드부터 맨 오른쪽노드까지 검사하며 문자열에 만약 더미노드라면 0, 더미노드가 아니라면 1을 추가한다.
  • 문자열에 저장된 이진수를 십진수로 변환한다.

---

문제 조건

• numbers : 이진트리로 만들고 싶은 수가 담긴 1차원 정수 배열
• 1 <= len(numbers) <= 10,000
• 1 <= nubers[i] <= int(1e15)

---

시행착오

• 포화이진트리의 특성을 이용해서 풀어야하는 문제임을 알았다. 
• 포화이진트리의 높이가 2^h-1이라는걸 알고 만약 2진수의 길이가 2^-1가 아니면 이진트리로 변환할 수 없다고 생각했다.
• 근데 아니었음 길이가 2^h-1이 될때까지 앞에 0을 붙여주면 되는거였다. 

---

문제해결 전략

• 포화이진트리의 노드의 개수는 2^h-1이다.
  이진트리의 높이를 구하고, 포화이진트리의 노드 개수에 맞도록 앞에 0을 추가한다. 
• 루트노드의 인덱스는 i//2이다. 루트노드는 무조건 존재해야 하므로 i//2번째 노드가 1인지 검사한다.
• 맨 아래층부터 만약 자식의 노드가 하나라도 1이면 부모노드가 1인지 검사한다. 

---

소스코드

def canExpressBinaryTree(num):
    binary = bin(num)[2:]

    h = 1
    while len(binary) > 2**h -1:
        h += 1

    binary = '0'*(2**h - len(binary) -1) + binary

    if binary[len(binary)//2] != '1':
        return 0

    for i in range(1, h):
        for j in range(0 + 2**(i-1)-1, len(binary), 2**(i+1)):
            if binary[j] == '1' or binary[j+2**i] == '1':
                if binary[j+2**(i-1)] != '1':
                    return 0

    return 1

def solution(numbers):
    answer = []

    for n in numbers:
        answer.append(canExpressBinaryTree(n))

    return answer