[Level 3] 표현 가능한 이진트리(Python)

프로그래머스

문제

이진 트리로 만들고 싶은 수가 이진 트리로 표현할 수 있다면 1, 없다면 0을 1차원 정수 배열에 담아 return

 

<제한 사항>

- 1 ≤ numbers의 길이 ≤ 10,000

- 1 ≤ numbers의 원소 ≤ 10^15

 

풀이 과정

풀이 시간: 1시간 30분

알고리즘: 구현, 트리

1. 이진수로 변환

2. 포화 이진트리 만들기

3. 만들어진 포화 이진트리가  이진트리로 표현 가능한지 확인

 

시간 복잡도: O(NlogM)

- N: 입력 배열 numbers의 길이

- M: 입력 배열에서 가장 큰 숫자

 

코드

import math


def solution(numbers: list) -> list:
    """
    :param numbers: 이진 트리로 만들고 싶은 수를 담은 1차원 정수 배열
    :return: numbers에 주어진 순서대로 하나의 이진 트리로 해당 수를 표현할 수 있다면 1, 표현할 수 없다면 0을 담은 1차원 정수 배열
    """
    answer = []  # 이진트리로 표현할 수 있는 수(1), 없는 수(0)
    for num in numbers: # 수를 하나씩 확인한다.
        bt = make_tree(num) # 포화 이진트리로 만들어준다.
        if check(bt): # 정상적인 포화 이진트리라면
            answer.append(1) # answer에 1을 추가
        else: # 아니라면
            answer.append(0) # answer에 0을 추가
    return answer


def make_tree(num: int) -> str:
    """
    십진수 num을 이진수로 변환 후, 포화 이진트리로 만드는 함수
    :param num: 주어진 십진수
    :return: (필요한 더미 노드를 추가한) 이진수
    """
    binary_num = bin(num)[2:] # 이진수로 변환
    h = math.ceil(math.log2(len(binary_num) + 1)) # 트리의 높이
    size = 2 ** h - 1 # 노드의 개수
    dummy = size - len(binary_num) # 더미 노드의 개수
    bt = '0' * dummy + binary_num # 포화 이진트리 크기보다 길이가 짧다면 0(더미)를 앞에 붙여준다. (뒤에 붙여주면 값이 변해서 안됨)

    return bt


def check(bt: str) -> bool:
    """
    포화 이진트리가 제대로 성립하는지 확인하는 함수
    :param bt: 이진수
    :return: 해당 이진수로 포화 이진트리가 제대로 성립한다면 True, 아니라면 False
    """
    if len(bt) <= 1: # 노드의 개수가 1개 이하이면 무조건 포화 이진트리임
        return True

    mid = len(bt) // 2
    left_tree = bt[:mid] # 왼쪽 자식 서브트리
    right_tree = bt[mid+1:] # 오른쪽 자식 서브 트리

    root = bt[mid] # 루트 노드
    left = left_tree[len(left_tree)//2] # 왼쪽 서브트리의 부모 노드
    right = right_tree[len(right_tree)//2] # 오른쪽 서브트리의 부모 노드

    if root == '0' and (left == '1' or right == '1'): # 더미노드인 경우 1인 자식 노드를 가질 수 없음
        return False
    else:
        return check(left_tree) and check(right_tree) # 재귀적으로 왼쪽 서브트리와 오른쪽 서브트리를 확인한다.​

이전에 풀어본 문제였는데도, 문제의 예제와 설명이 불친절한 편이라 문제를 다시 이해하는데 한참 걸렸다.

트리 성질을 까먹어서 다시 생각하는데도 시간이 꽤 걸렸던 문제로, 시간이 지나고 다시 한번 풀어봐야 할 것 같다.