[99클럽/파이썬 챌린저/32일차] 표현 가능한 이진트리

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

 

문제 설명
당신은 이진트리를 수로 표현하는 것을 좋아합니다. 이진트리를 수로 표현하는 방법은 다음과 같습니다. 이진수를 저장할 빈 문자열을 생성합니다. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다. 문자열에 저장된 이진수를 십진수로 변환합니다. 이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다. 당신은 수가 주어졌을 때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다. 이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항
1 ≤ numbers의 길이 ≤ 10,000
1 ≤ numbers의 원소 ≤ 10^15

입출력 예

numbers	result
[7, 42, 5]	[1, 1, 0]
[63, 111, 95]	[1, 1, 0]

 

 

분할 정복 DFS로 해결했다.

먼저 주어진 숫자를 이진수로 변환하고 포화 이진트리의 개수에 맞게 수정하였다.

 

루트에서부터 자식을 탐색하면서 이상이 있는지 여부를 확인했다.

이상이 없다면 가능하며 이상이 있으면 불가능이라고 판단했다.

 

 

def solution(numbers):
    def divide(l, i, r):
        if r == 0: return True
        if l[i] == '0':
            if l[i-r] == '1' or l[i+r] == '1': return False
        
        return divide(l, i-r, r//2) and divide(l, i+r, r//2)
    
    answer = []
    for num in numbers:
        bi = bin(num)[2:]
        n = len(bi)
        cur = 1
        while n > cur: cur *= 2
        bbi = ['0'] * (cur-n-1) + list(bi)
            
        answer.append(1 if divide(bbi, len(bbi)//2, (len(bbi)+1)//4) else 0)
    
    return answer

 

---