2023 KAKAO BLIND RECRUITMENT - 표현 가능한 이진트리

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

포화 이진 트리: 트리내 요소의 개수 = 2 ** n - 1

'0' 노드의 아래 노드는 모두 '0'이어야 한다. 

def solution(numbers):
    def is_tree(s, parent):
        if parent == '0' and not all(child == '0' for child in s):
            return False
        if len(s) == 1:
            return True
        return is_tree(s[:(center := len(s) // 2)], s[center]) and is_tree(s[center + 1:], s[center])

    def to_bin(num):
        s = bin(num)[2:]
        return '0' * (2 ** (int(log2(len(s))) + 1) - 1 - len(s)) + s

    from math import log2
    return [1 if is_tree((s := to_bin(num)), s[len(s) // 2]) else 0 for num in numbers]

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.04ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.2MB)
테스트 4 〉	통과 (0.18ms, 10.3MB)
테스트 5 〉	통과 (0.42ms, 10.2MB)
테스트 6 〉	통과 (0.86ms, 10.2MB)
테스트 7 〉	통과 (1.01ms, 10.3MB)
테스트 8 〉	통과 (0.53ms, 10.3MB)
테스트 9 〉	통과 (5.58ms, 10.3MB)
테스트 10 〉	통과 (47.51ms, 11MB)
테스트 11 〉	통과 (51.36ms, 11.4MB)
테스트 12 〉	통과 (48.49ms, 11.4MB)
테스트 13 〉	통과 (43.66ms, 11MB)
테스트 14 〉	통과 (41.91ms, 11.1MB)
테스트 15 〉	통과 (31.86ms, 10.7MB)
테스트 16 〉	통과 (111.71ms, 11.4MB)
테스트 17 〉	통과 (119.57ms, 11.4MB)
테스트 18 〉	통과 (95.79ms, 11.1MB)
테스트 19 〉	통과 (93.66ms, 11.1MB)
테스트 20 〉	통과 (55.20ms, 10.7MB)

읽기 편하게 풀어보면..

from math import log2


def is_tree(s, parent):
    if parent == '0':
        if not all(child == '0' for child in s):
            return False
    if len(s) == 1:
        return True
    center = len(s) // 2
    return is_tree(s[:center], s[center]) and is_tree(s[center + 1:], s[center])


def to_bin(num):
    s = bin(num)[2:]
    s_length = int(log2(len(s))) + 1
    digit = 2 ** s_length - 1
    return '0' * (digit - len(s)) + s


def solution(numbers):
    answer = []
    for num in numbers:
        s = to_bin(num)
        if is_tree(s, s[len(s) // 2]):
            answer.append(1)
        else:
            answer.append(0)
    return answer

로그를 쓰지 않고 푼다면.. 

def is_tree(s, parent):
    if parent == '0':
        if not all(child == '0' for child in s):
            return False
    if len(s) == 1:
        return True
    center = len(s) // 2
    return is_tree(s[:center], s[center]) and is_tree(s[center + 1:], s[center])


def solution(numbers):
    answer = []
    for number in numbers:
        bs = bin(number)[2:]
        digit = 0  # 포화 이진트리가 되기 위한 문자열의 길이
        for i in range(51):
            digit = 2 ** i - 1
            if digit >= len(bs):
                break
        bs = '0' * (digit - len(bs)) + bs
        answer.append(1 if is_tree(bs, bs[len(bs) // 2]) else 0)
    return answer

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.05ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.3MB)
테스트 4 〉	통과 (0.21ms, 10.3MB)
테스트 5 〉	통과 (0.47ms, 10.1MB)
테스트 6 〉	통과 (0.78ms, 10.3MB)
테스트 7 〉	통과 (1.21ms, 10.2MB)
테스트 8 〉	통과 (0.84ms, 10.2MB)
테스트 9 〉	통과 (6.16ms, 10.2MB)
테스트 10 〉	통과 (53.36ms, 11MB)
테스트 11 〉	통과 (60.98ms, 11.2MB)
테스트 12 〉	통과 (57.60ms, 11MB)
테스트 13 〉	통과 (52.23ms, 11MB)
테스트 14 〉	통과 (47.56ms, 11MB)
테스트 15 〉	통과 (35.98ms, 10.6MB)
테스트 16 〉	통과 (144.51ms, 11.2MB)
테스트 17 〉	통과 (112.64ms, 11.3MB)
테스트 18 〉	통과 (101.80ms, 11.1MB)
테스트 19 〉	통과 (95.21ms, 11MB)
테스트 20 〉	통과 (59.65ms, 10.5MB)