문제

Programmers: 표현 가능한 이진트리

설명: 포화이진트리를 이진수로 표현할 때 주어진 십진수를 만들 수 있는지 판단하여라

풀이

기본적으로 주어진 이진수가 잘못된 트리인지를 판단하는 문제이다.
- 잘못된 트리라는 것은 루트 노드가 없을 때 자식 노드가 있으면 잘못된 트리이다.
- 이를 판단해주면 된다.
- 포화이진트리를 중위순회할 때는 항상 루트 노드가 정 중앙에 오게 된다.
- 따라서 현재 주어진 이진수의 정 중앙을 확인하고,
- 그 중앙 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리로 두고 재귀적으로 판단해 나가면 된다.
만약 현재 서브트리에서 루트 노드가 없다면 자식 노드는 반드시 없어야한다.
- 이를 재귀 함수의 한 인자로 넣어주어 부모 노드가 $1$인지 $0$인지, 현재 루트 노드가 $1$인지 $0$인지에 따라 총 $4$가지 경우의 수에 따라 답을 판단해준다.
포화이진트리를 만들기 위해서는 노드의 개수가 $2^{높이} - 1$이 되어야한다.
- 하지만 주어진 십진수를 이진수로 변경했을 때 각 digit의 길이가 위의 노드의 개수와 동일하지 않다.
- 따라서 부족한 만큼 앞에 0을 채워넣어 개수를 맞춰준다.
여기서 중요한 점은 그 십진수를 만들기 위한 노드의 개수를 모른다는 것이다.
- 하지만 최대 노드의 개수를 알 수 있다.
- 주어지는 십진수는 최대 $10^{15}$이고 이는 대충 $2^{50}$ 보다 작으므로 이진수가 $50$자리 이하로 이루어져있다는 것을 알 수 있다.
- 그렇다면 노드의 개수는 $1, 3, 7, 15, 31, 63$ 중 하나일테고 모든 경우의 수를 따져가며 잘못된 트리인지 판단하면 된다.

오늘의 회고

트리의 성질을 이용한 재밌는 문제였다.
엄청나게 수학적인 문제 같지만 사실 적당한 BF와 재귀가 필요한 좋은 문제!
처음 이 프로그램을 시작했을 때보다 확실히 파이썬으로 알고리즘 실력이 늘었다. PCCP를 꼭 따보이겠다!

Code

# Programmers150367.py
def can(num, has_root):
    n = len(num)
    if n == 0:
        return True

    root = n // 2
    left = num[:root]
    right = num[root + 1:]
    if has_root:
        if num[root] == "1":
            return can(left, True) & can(right, True)
        else:
            return can(left, False) & can(right, False)
    else:
        if num[root] == "1":
            return False
        else:
            return can(left, False) & can(right, False)

def solution(numbers):
    ans = []

    NODES = [1, 3, 7, 15, 31, 63]
    for number in numbers:
        bin_num = bin(number)[2:]
        n = len(bin_num)

        can_make = False
        for node in NODES:
            if n <= node:
                if can('0' * (node - n) + bin_num, True):
                    can_make = True
                    break

        ans.append(1 if can_make else 0)

    return ans