표현 가능한 이진트리

문제

카카오 2023 Blind Recruitment 문제다 :

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

접근 방식

이 문제는 이진 트리에 대한 배경지식 + 그 성질을 활용한 약간의 응용력이 필요한 문제였다. 왼쪽 서브 트리, 루트, 오른쪽 서브 트리로 분할할 수 있다는 이진 트리의 성질을 활용해 재귀적으로 분할해가며 트리의 유효성을 검사하는 방식으로 풀었다.

포화 이진 트리가 가장 중요한 힌트다.

포화 이진 트리란, 서브트리까지 모두 빈 곳 없이 꽉찬 이진 트리로, 노드의 개수는 2 ** 트리 높이 - 1이다.

주어진 숫자를 이진수로 변환했을 때, 이를 포화 이진 트리로 표현하기 위해서는 그 노드 수를 맞출 필요가 있다. (처음에 우수수 틀렸을 땐 단순히 홀수개면 된다고 착각했다)

해당 이진수가 valid tree기 위해서는, 부모 노드가 null이면 안된다는 사실을 유추할 수 있다. 다만 여기서 부모 노드가 null일 때, 자식 서브 트리들도 모두 null인 경우를 고려해야 한다.

ex. 15 -> 1111 -> 0001111 (포화 이진 트리 형태)

트리 분할
=> 000 (=left) / 1 (=root) / 111 (=right)

이런 테스트케이스에서 단순히 부모 노드만 검사한다면 왼쪽 서브 트리는 유효 하지 않다. 하지만 부모 노드 + 자식 노드 모두 null인 경우므로, 부모가 null이더라도 통과시켜야 한다.

이런 케이스를 고려해

if bnum[mid] == '0' and not is_all_null(bnum)

조건으로 유효성을 검사하도록 수정했다.

코드

def is_all_null(bnum):  # 양쪽 자식 트리 검사
    half = len(bnum) // 2
    return bnum[:half].count('0') == bnum[half + 1:].count('0') == half


def is_valid_bt(bnum):
    if len(bnum) == 1:  # 노드가 하나면 상관없이 통과
        return True

    mid = len(bnum) // 2
    # 부모 null + 양쪽 자식 트리 모두 null 이면 PASS, 하나라도 노드가 존재하면 FALSE
    if bnum[mid] == '0' and not is_all_null(bnum):
        return False

    return is_valid_bt(bnum[:mid]) and is_valid_bt(bnum[mid + 1:])


def find_upper(n):  # 포화 이진 트리 맞추기 위해
    h = 0
    while 2 ** h - 1 < n: h += 1
    return 2 ** h - 1


def solution(numbers):
    res = []
    for number in numbers:
        bnum = format(number, 'b')
        bnum = '0' * (find_upper(len(bnum)) - len(bnum)) + bnum  # 포화 이진 트리 노드 개수 맞추기

        res.append(int(is_valid_bt(bnum)))

    return res