[Python] 표현 가능한 이진 트리

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

2023 카카오 블라인드 기출 문제인 '표현 가능한 이진 트리'를 풀이하고,
정리한 내용입니다.

1) 첫 풀이 시도

• 주어진 숫자를 이진수 문자열로 변환하고, 길이가 짝수인 경우 앞에 '0'을 더했습니다
• '0'을 더한 후에, 해당 문자열에 대해서 이진 탐색을 진행했습니다
• 이진 탐색을 진행하면서 중간 위치에 있는 값을 확인하고,
  해당 값이 '0'인 경우에 False를 리턴하고,
  '1'인 경우에 다시 재귀적으로 이진 탐색을 진행했습니다
• 이진 탐색을 진행하다가 길이가 1이 되는 경우에 True를 리턴했습니다.

2) 내 첫 풀이 코드

• 결과적으로 이 코드는 '런타임 에러'를 발생시켰습니다.

def checkBinary(start, end, numStr):

    if start == end:
        return True

    mid = (start + end) // 2

    if numStr[mid] == '1':
        return checkBinary(start, mid-1, numStr) and checkBinary(mid+1, end, numStr)
    else:
        return False


def toBinary(num):
    numStr = ""

    while num != 0:
        remain = num % 2
        numStr += str(remain)
        num = int(num // 2)

    return numStr[::-1]


def solution(numbers):
    answer = []

    numStr = ''

    for num in numbers:
        numStr = toBinary(num)
        if len(numStr) % 2 == 0:
            numStr = '0' + numStr
        res = checkBinary(0, len(numStr)-1, numStr)
        if res == True:
            answer.append(1)
        else:
            answer.append(0)

    return answer

3) 첫 풀이 코드의 문제점

(1) 이진수로 변환한 문자열은 '완전 이진 트리'를 만족시켜야 한다는
문제의 조건을 정확하게 이해하지 못했습니다
'완전 이진 트리'가 되기 위해서 문자열의 길이는 항상 2^n-1
즉, 3, 7, 15, ...에 해당하는 길이를 가져야 합니다.
따라서 문자열의 길이를 확인하고, 해당 길이에 해당하지 않는다면
그만큼 앞에 '0'을 추가해줘야 합니다.

(2) 이진수로 변환한 문자열의 중간 위치에 '0'이 있다고 해서
바로 False를 리턴해서는 안됩니다.
왜냐하면 해당 위치가 '0'이라 하더라도, 해당 위치의 좌우가 모두 '0'이라면 해당 위치에 노드가 존재하지 않아도 되므로 문제가 없기 때문입니다.
따라서 이에 대해서 '0'을 기준으로 좌우에 '1'이 존재하는지
추가적으로 검사를 해야 합니다.

4) 답안 코드

• 답안 코드는 프로그래머스에서 참고했습니다.

def check(s):
    if len(s) == 1:
        return True

    center = len(s) // 2

    if s[center] == '0':
        if '1' in s[:center] or '1' in s[center + 1:]:
            return False

        else:
            return True
    else:
        if check(s[:center]) and check(s[center + 1:]):
            return True

        else:
            return False    


def make_zeropadding_binary(number):
    bin_str = bin(number)[2:]
    idx = 1
    while len(bin_str) > (2****idx)-1:
        idx += 1
    length = 2 **** idx - 1
    return '0' * (length - len(bin_str)) + bin_str


def solution(numbers):
    return [1 if check(make_zeropadding_binary(number)) else 0 for number in numbers]

• 답안 코드에서 배운 점은 다음과 같습니다.

(1) bin(number)[2:]를 통해 숫자를 이진수 문자열로 쉽게 변환할 수 있습니다.

(2) 완전 이진 트리의 노드 개수를 기준으로 length를 구하고,
이진수로 변환한 숫자의 길이와 차이만큼 0을 더해줍니다.

(3) 해당 문자열을 이진 탐색하면서, 답을 구합니다.