[프로그래머스] 표현 가능한 이진트리 - 파이썬/분할정복, 재귀

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

# 문자열이 True인지 False인지 확인하는 함수
def check_str(string):

    if len(string)==1:
        return True

    left = string[: len(string) // 2]
    right = string[ (len(string) // 2)+1:]

    if len(string)==3:
        if string == '000':
            return True
        elif string[1] == '1':
            return True
        else:
            return False

    if string[len(string)//2] == '1':
        if check_str(left) and check_str(right):
            return True
        else:
            return False

    if string[len(string)//2] == '0':
        if '1' not in left and '1' not in right:
            return True

# n이 2의 거듭제곱임을 확인하는 함수
def ischeck(n):
    return (n & (n-1)) ==0

def solution(numbers):
    answer = []

    for i in numbers:
        bin_num = bin(i)[2:]
        while not ischeck(len(bin_num)+1):
            bin_num = '0' + bin_num

        if check_str(bin_num):
            answer.append(1)
        else:
            answer.append(0)

    return answer

문제를 쉽게 말하면 포화이진트리형태로 바꿨을때 이게 가능한 형태인지 판별하는 문제이다.

문제의 예시로 주어진 42를 판별하자고 하자

42는 이진수로 101010 이다.

포화이진트리는 노드갯수가 (2^n)-1개이므로 이진수의 문자열 길이가 (2^n)-1개가 아니라면 그만큼 앞에 0을 붙여준다.

즉, 42는 이진수로 0101010이 된다.

이를 포화이진트리의 형태로 나타내면 위의 그림과 같다. 검은 선은 실제 형태이고 빨간선은 문제에서 만든 더미노드와 연결되는 선이다.

값이 0인 더미노드에서 값이 1인 실제 노드가 뻗어나가는 경우가 없으므로 42는 이진트리로 표현할 수 있는 수인 것이다.

그래서 문제를 아래처럼 접근했다.

전체를 절반으로 나눠서 좌,우를 체크하는데

case1) 가운데 숫자가 1이라면, 좌우 모두 True를 반환해야 이진트리로 표현가능한 수이다.

case2) 가운데 숫자가 0이라면, 좌우 문자열이 모두 0이여야 이진트리로 표현 가능한 수이다.

case1은 점점 작은 단위로 쪼개진다.

그래서 노드가 3개일때를 최소단위로 보았다.

노드가 3개일때 000 혹은 가운데 수가 1인 경우는 True, 그 외에는 False를 반환한다.

이러한 방법으로 최소 단위에서 점점 타고올라가서 전체를 판별하는 문제이다.