[프로그래머스] 2023 Kakao Blind Recuiment : 표현 가능한 이진트리

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

프로그래머스

📄 문제개요

• 특정 숫자가 주어질때 해당숫자를 이진수로 만들고, 이진수를 만든뒤, 포화 이진트리를 만든다.
• 예를들어 포화 이진트리는 아래와 같다.
• 루트노드가 1이면 자식노드는 0또는 1을 갖는다.
• 루트노드가 0이면 자식노드들도 0이 되어야한다.

🤔 문제분석

• 특정숫자를 이진수로 만든뒤 포화 이진트리로 만들어야한다.
• 높이가 n일때, 포화 이진트리는 노드의 개수가 2^n -1 를 갖는다.
• 숫자에 왼쪽에 ‘0’을 추가하면 숫자값은 바뀌지 않는다.
• 따라서 포화 이진트리는 노드의 개수를 구하고, 현재 만든 이진수와 노드의 개수를 뺀 나머지를 0으로 왼쪽에 채운다.
• 새로 만든 이진수를 아래의 2개의 조건으로 나누어 푼다.
  • 루트노드가 1이면 왼쪽, 오른쪽 노드 그룹이 올바른 노드인지 확인한다.
  • 루트노드가 0이면 모든 자식노드는 0이다.

📝 의사코드

1. 숫자를 입력받아 이진수로 바꾼다.
2. 이진수의 길이를 구하고, 만들 수 있는 최소 포화 이진트리 개수를 구한다.
3. 최소 포하 이진트리 개수 - 현재의 이진트리 = 0이 만들어질 개수
4. 0이 만들어질 개수를 현재의 이진트리 왼쪽끝에 추가한다.
5. 현재 이진수가 올바른 트리인지 확인한다.
   1. 루트노드가 1이면 분할정복하여 왼쪽, 오른쪽 각각의 올바른 트리인지 확인한다.
   2. 루트노드가 0이면 루트노드 기준으로 왼쪽, 오른쪽은 모두 0이 되어야한다. 그렇지 않다면 올바른 트리가 아니다.

💻 코드

def make_binary(number):
    if number == 0:
        return '0'
    
    temp = ''
    while number > 0:
        temp += str(number % 2)
        number = number // 2
        
    return temp[::-1]

def is_binary(binary):
    if len(binary) == 1:
        return True
    
    center = len(binary)//2
    if binary[center] == '1':
        return is_binary(binary[:center]) and is_binary(binary[center+1:])
    else:
        for l in range(center):
            if binary[l] == '1':
                return False
        
        for r in range(center+1, len(binary)):
            if binary[r] == '1':
                return False
            
        return True

        

def solution(numbers):
    answer = []
    for number in numbers:
        temp = make_binary(number)
        h = 0
        for i in range(1, int(1e9)):
            if pow(2,i) - 1 >= len(temp):
                h = pow(2,i) - 1
                break
        temp2 = '0'* (h - len(temp))
        
        if is_binary(temp2 + temp):
            answer.append(1)
        else:
            answer.append(0)
            
    return answer

🎯 피드백 및 개선사항

• 문제에서 루트노드가 1이면 왼쪽노드집합, 오른쪽노드집합이 올바른 이진트리인지 확인하고, 루트노드가 0이면 자식노드가 모두 0이 되어야하는 조건을 생각해 내는것이 문제의 핵심 포인트이다.
• 높이가 n일때, 이진 포화 트리의 노드의 개수가 2^n -1 이라는것을 파악해 내는것이 핵심 포인트이다.

❓다른사람은 어떻게 풀었을까?

• 문제의 접근 방식은 똑같습니다.

def dnc(num, left, right):
    if left == right:
        return [True, int(num[left])]

    mid = (left + right) // 2
    root = int(num[mid])

    left_subtree = dnc(num, left, mid - 1)
    right_subtree = dnc(num, mid + 1, right)

    flag = left_subtree[1] or right_subtree[1]

    if flag == 1 and root == 0:
        return [0, 0]

    return [left_subtree[0] and right_subtree[0], root]

def get_answer(num):
    tmp = ''
    while num > 0:
        tmp = tmp + str(num % 2)
        num //= 2
    size = 1
    while len(tmp) > pow(2, size) - 1:
        size += 1
    while len(tmp) < pow(2, size) - 1:
        tmp += '0'

    return int(dnc(tmp, 0, len(tmp) - 1)[0])

def solution(numbers):
    answer = [get_answer(num) for num in numbers]
    return answer