프로그래머스 - 표현 가능한 이진트리

문제 주소

def makeBinaryNumber(number):
    reverseBinaryNumber = []
    while number != 1:
        reverseBinaryNumber.append(str(number % 2))
        number //= 2
    reverseBinaryNumber.append("1")
    binaryNumber = ''.join(reverseBinaryNumber[::-1])
    binaryTreeSize = 1
    while binaryTreeSize < len(binaryNumber):
        binaryTreeSize = (binaryTreeSize + 1) * 2 - 1
    binaryNumber = "0" * (binaryTreeSize - len(binaryNumber)) + binaryNumber
    return binaryNumber

def checkPossible(start, end, binaryString):
    if start == end:
        return binaryString[start]
    mid = (start + end) // 2
    left = checkPossible(start, mid-1, binaryString)
    if not left or (binaryString[mid] == "0" and left == "1"): return False
    right = checkPossible(mid+1, end, binaryString)
    if not right or (binaryString[mid] == "0" and right == "1"): return False
    if left == "0" and right == "0" and binaryString[mid] == "0": return "0"
    return "1"

def solution(numbers):
    answer = []
    for number in numbers:
        binaryNumber = makeBinaryNumber(number)
        if checkPossible(0, len(binaryNumber)-1, binaryNumber):
            answer.append(1)
        else:
            answer.append(0)
    return answer

문제 풀이

대략적인 개요

1. 일단 숫자를 가지고 이진수로 만든다.
2. 그 이진수를 가지고 가능한 포화 이진트리를 만든다
3. 포화 이진트리가 가능한지 확인한다.

디테일한 설명

1. 숫자를 이진수로 만드는 과정은 흔히 사용하는 방법을 이용해서 만들었습니다. 숫자를 계속해서 2로 나누면서 나머지를 저장하고 그 나머지들을 뒤집으면 우리가 원하는 이진수를 얻을 수 있습니다.

2. 이진수를 만든 후에 이 이진수로 만들 수 있는 포화 이진트리의 크기는 이진수의 길이보다 크거나 같은 2 ** n - 1중 가장 작은 숫자입니다.

3. 그리고는 재귀를 이용하여 가능한 이진트리인지를 체크합니다.

   부모는 더미 노드인데 자식노드는 더미노드가 아닌경우를 체크하면 이 이진트리가 가능한 트리인지 불가능한 트리인지 확인 할 수 있습니다.

   1. 리프노드까지 계속 내려갑니다.
   2. 리프노드에서는 "0" 혹은 "1"을 리턴합니다.
   3. 자식 노드가 "1"을 리턴하지만 부모노드가 "0"의 값을 가지면 불가능한 이진트리이므로 False를 리턴합니다.
   4. False를 리턴하면 뒤도 돌아보지 말고 재귀함수를 끝냅니다.
   5. 부모와 자식 모두 "0"의 값을 가지면 "0"을 리턴합니다.
   6. 부모와 자식 중 누구라도 "1"을 가진다면 "1"을 리턴합니다.
   7. False를 리턴하지 않으면 가능한 이진트리라고 판단합니다.