문제

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

접근방식

제일 어질어질한 문제였다고 생각한다.
문제에 대한 설명도 친절한 듯 불친절하며, 포화 이진트리에 대한 개념이 명확히 잡혀있지 않으면 너무나도 난이도가 높아지는 문제라고 생각한다. 거기에 이진트리 순회에 대한 개념도 들어가 있다.

카카오 테크 블로그의 해설을 보고 풀었어도, 한참 걸렸던 문제였다.
정말 힘들게 풀었던 문제인데, 나 같은 경우는 혼자서 함정을 만들면서 풀었었다.

<해결 포인트>
1. 포화 이진 트리란?
2. 어떤 수 건 포화 이진 트리로 무조건 만들 수 있다. (왼쪽에 0을 붙이면 된다.)
3. 2진수의 배열이 포화 이진 트리를 중위 순회한 리스트이다.
4. 포화 이진 트리를 중위 순회한 리스트의 가운데 값은 해당 트리의 root노드이다.
5. 한 부모노드의 값이 0이라면 해당 노드의 자식 노드 뿐만 아니라, "모든" 자식 노드에는 1이 존재할 수 없다.

문제의 설명에 트리가 그러져 있지만, 그냥 모든 불완전한 트리를 포화이진트리로 만들기 위해 빈 부분을 모두 0으로 채우라는 말과 같다고 보고 접근하면 쉽다.

포화이진트리는 쉽게 말하면 트리의 노드에 빈 노드가 아예 없는 이진트리를 말한다.
즉 노드의 개수가 트리의 높이에 따라 정해진다.
포화이진트리에서 트리의 노드의 개수는 h가 트리의 높이 일때
노드의 개수 = 2^h-1
로 정의 된다.

그러므로 100110과 같은 2진수는 노드의 개수가 6개이지만 포화 이진트리가 되기 위해서는 2^3-1인 7개의 노드가 필요하므로 2진수의 왼쪽에 0을 하나를 더 붙이면 된다.

10111011과 같은 2진수는 노드의 개수가 8개 이므로 포화이진트리가 되기 위해서
2^4-1 인 15개의 노드가 필요하므로 7개의 0을 왼쪽에 붙여주어 000000010111011과 같은 문자열을 만들어 주어야한다.

이제 만들어진 포화이진트리의 리스트를 분할하여 탐색해주면 된다.
위에서 중위순회한 리스트의 가운데 값이 root노드이다를 적극 활용하면 쉽게 탐색을 할 수 있다.
0000000|1|0111011의 중앙 노드는 1이므로 1의 좌측은 좌측 이진트리, 우측은 우측의 이진트리이다.

000|0|000 과 011|1|011로 나뉜다.

이제 여기서 우측 트리를 한번 보자. 우측트리의 root노드는 1이다.

좌측 트리는 011과 011로 나뉘게 되며 두 트리 모두 root노드가 1이므로 해당 포화이진트리로 표현이 가능하다.

위의 예시 같은 경우는 모든 root노드가 1인 경우였지만, 0일 경우는 어떨까?

011|0|011 이었다면 root노드가 0이지만 좌측 자식과 우측자식이 1이므로 포화 이진트리가 성립 할 수 없다.

주의점!
root 노드가 0일때 좌측 자식노드와 우측 자식노드만 1이 아니면 성립된다고 생각하고 처음에 문제를 풀었으나 처참하게 정답이 틀렸다고 나왔다.
"모든 자식 노드가 1이 아니어야" 문제에서 포화이진트리가 성립된다는 점을 간과했었다.

즉 root 노드가 0인 경우 root노드를 기점으로 왼쪽 리스트와 오른쪽리스트 모두 1이 존재하면 안되는 점을 체크해야 모든 테스트 케이스를 통과할 수 있다.

정답코드

#분할 탐색
def division_search(left, right, arr):
    global flag
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    if arr[mid] == '0':
        for i in range(left, mid):
            if arr[i] == '1':
                flag = False
                return
        for i in range(mid + 1, right + 1):
            if arr[i] == '1':
                flag = False
                return
    division_search(left, mid - 1, arr)
    division_search(mid + 1, right, arr)
    
def solution(numbers):
    global flag
    answer = []
    for n in numbers:
        flag = True
        n = bin(n).replace('0b', '')
        index = 1
        node_count = 0
        while 1:
            if pow(2, index) - 1 >= len(n):
                node_count = pow(2, index) - 1
                break
            index += 1
        n = list(('0' * (node_count - len(n))) + n)
        division_search(0, len(n) - 1, n)
        if flag:
            answer.append(1)
        else:
            answer.append(0)
    return answer

코드해설

재귀적으로 트리를 분할하여 체크를 하다보니 전역변수를 사용하였습니다.(ㅠ)

  n = bin(n).replace('0b', '')

저는 파이썬으로 2진수로 변환할때 bin함수를 이용하여 2진수로 변환하고 앞의 0b를 떼는 방식으로 변환합니다.(편하더라구요!)

 while 1:
            if pow(2, index) - 1 >= len(n):
                node_count = pow(2, index) - 1
                break

포화이진트리를 만들기 위해 현재 2진수 노드 개수보다 포화 이진트리의 노드의 개수가 크거나 같은 가장 최소의 node_count를 찾는 코드입니다.

def division_search(left, right, arr):
    global flag
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    if arr[mid] == '0':
        for i in range(left, mid):
            if arr[i] == '1':
                flag = False
                return
        for i in range(mid + 1, right + 1):
            if arr[i] == '1':
                flag = False
                return
    division_search(left, mid - 1, arr)
    division_search(mid + 1, right, arr)

이진 탐색과 비슷한 코드입니다.
리스트의 시작인덱스와 마지막 인덱스를 체크하고 mid값을 체크하여 mid 노드가 0이라면 mid를 기점으로 좌측과 우측 1이 존재한다면 포화이진트리가 불가능하므로, 바로 flag를 False로 변경하고 종료합니다.