표현 가능한 이진 트리 [2023 KAKAO BLIND RECRUITMENT]

1) 문제 접근 방법

- 이 문제는 포화 이진 트리의 개념을 이해하고, 그 조건에 맞게 구현을 하는 문제이다. 

  우선은, 주어진 숫자를 이진수로 변환하고, 자리수를 2^n-1로 맞춰준다.

  자리수를 2^n-1로 맞춰준 이유는 그렇게 해야 포화 이진 트리가 될 수 있기 때문이다. 

 

- 그 다음에 이분 탐색을 통해서 노드를 탐색하는데,

   만약에 이분 탐색 시 서브 트리의 루트 노드가 0이라면, 해당 서브 트리의 자손 노드들에서는 1이 존재하면 안된다. 

   왜냐하면 그렇게 하는 것은 트리의 정의에 어긋 나기 때문이다. 

 

- 이를 위해 flag라는 변수를 통해서 판단을 해줬고, 서브 트리의 루트 노드가 0일 때는, 

   flag를 True로 처리하여, 서브 트리의 자손 노드에 전달되도록 하였다. 

 

- 그리고 만약에 서브 트리의 자손 노드 중에서 하나라도 1이 발견되면, return False를 하도록 하였다. 

 

- 서브 트리의 루트 노드가 0일 때, 해당 서브 트리의 자손 노드들에서는 1이 존재하면 안된다는 아이디어가

   제일 중요한 문제라고 할 수 있다. 

 

 

2) 소스 코드  

def binarySearch(start, end, res, flag):
    

    if start == end:
        if flag == False:
            return True 
        else: 
            if res[start] == '1':
                return False
            else:
                return True
            
    mid = (start+end) // 2 
    
    if flag == True:
    	if res[mid] == '1':
        	return False 
        
    
    if res[mid] == '1':
        return binarySearch(start, mid-1, res, False) and binarySearch(mid+1, end, res, False)
    else:
        return binarySearch(start, mid-1, res, True) and binarySearch(mid+1, end, res, True)
    
    
    
    
    
    



def changeToBinary(num):
    
    res = ""
    
    while num != 0:
        
        r = num % 2 
        
        res += str(r)
        
        num = num // 2 

    binaryLen = len(res)
    
    n = 0
    m = 1 
    
    while True: 
        
        N = 2**n-1
        M = 2**m-1 
        
        if N < binaryLen and binaryLen <= M:
            if binaryLen == M:
                break
            else:
                gap = M-binaryLen 
                
                for i in range(gap):
                    res += '0'
                
                break     
        else:
            n += 1 
            m += 1 
    
    
    
        
    return res[::-1]


def solution(numbers):
    
    answer = []
    
    for num in numbers:
        res = changeToBinary(num)
        ans = binarySearch(0, len(res)-1, res, False)
        
        if ans == True:
            answer.append(1)
        else:
            answer.append(0)
            
    
        
    return answer