[프로그래머스 / 파이썬] 2023 KAKAO BLIND RECRUITMENT 표현 가능한 이진트리

프로그래머스에 존재하는 연습 문제이다.

문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/150367

프로그래머스

---

문제 해석

이진트리가 주어진다. 이를 이진 포화트리로 바꾸었을 때 더미노드는 0, 존재하는 노드는 1로 가정하여 왼쪽부터 읽어 2진수로 변경할 수 있다.
이때 문제에서 숫자가 주어졌을 때 해당 숫자를 이진트리로 표현할 수 있는지 판단하는 문제이다.

---

문제 풀이

1. 자릿수 변경

먼저 이 문제를 해결하기 위해서 주어진 수를 이진수로 변경한 뒤, 이진 포화트리에 맞게 자릿수를 맞추어 주어야 한다.
예시로 3의 입력을 받았을 경우 이진수는 "11" 로 변환되지만 이진 포화트리에 맞게 자릿수를 바꾸어 "011"로 맞추어야 한다.

# 2진수 변환
num_bin = bin(num)[2:]
# 2^n - 1꼴의 자릿수를 가져야함.
digit = 2 ** (int(math.log(len(num_bin), 2)) + 1) - 1
num_bin = "0" * (digit - len(num_bin)) + num_bin

2. 이진 포화트리로 바꿀 수 있는지 확인

다음은 자릿수를 맞추어준 이진수를 통해 이진 포화트리로 표현할 수 있는지 확인해야 한다.
먼저 이진 트리를 만족하기 위해서는 자식 노드 위에는 항상 부모 노드가 존재해야 함을 기억하자.

다음은 문제에서 주어진 이진 포화트리를 표현하는 순서이다.
이 그림을 통해 부모노드의 자식 노드는 [0~부모노드]의 가운데, [부모노드~끝까지]의 가운데에 존재하는 것을 알 수 있다.

예시로 [1, 2, 3, 4, 5, 6, 7]을 들어보자.

1번 예시에서 부모노드는 4이다. 이때의 왼쪽 자식은 [1, 2, 3]의 가운데 수인 2가 된다.
마찬가지로 우측 자식은 [5, 6, 7]의 가운데 수인 6이 된다.

따라서 2번 예시에서도 2의 자식노드는 1, 3 6의 자식노드는 5, 7이 된다.


위 사실을 통해 mid를 자식으로 세팅하여, 부모노드의 존재를 재귀적으로 받아
부모 노드가 존재하지 않고, 내가 존재하는 경우 False를 반환
이외의 경우는 참을 반환하도록 하여 재귀적으로 답을 구해주었다.
mid 기준으로 좌우를 나누어 매번 확인하기 때문에 주어진 수의 최댓값이 10^15이지만 log n의 시간복잡도로 문제를 해결할 수 있다.

---

문제 코드

import math
def check(num_bin, prev_parent):
    # 중앙값(자손) 기준으로 재귀적으로 확인
    mid = len(num_bin) // 2
    if num_bin: son = (num_bin[mid] == '1')
    else: return True
    
    # 내가 존재하면 부모가 존재해야함.
    if son and not prev_parent:
        return False
    else:
        return check(num_bin[mid + 1:], son) and check(num_bin[:mid], son)

def sol(num):
    # 1은 항상 참
    if num == 1: return 1

    # 2진수 변환
    num_bin = bin(num)[2:]
    # 2^n - 1꼴의 자릿수를 가져야함.
    digit = 2 ** (int(math.log(len(num_bin), 2)) + 1) - 1
    num_bin = "0" * (digit - len(num_bin)) + num_bin
    # print(digit, num_bin)
    
    # 누군가의 부모 노드는 항상 존재해야함. 
    if num_bin[len(num_bin) // 2] == '1'and check(num_bin, True): return 1
    else: return 0

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