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

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

프로그래머스

 

 

 

<문제 풀이>

- 이 문제를 풀기 위해서는 트리구조와 순회방법에 대해 알아야 했다.

- 먼저 포화이진트리로 형태를 맞춰주기 위해 주어진 수를 이진수로 변환 후 부족한 자리는 0으로 채워넣는다.

- 문제의 예제에서는 트리는 0이 위치한 자리엔  노드가 존재하지 않고 1이 위치한 곳만 실제 형태로 남아있다.

- 이진트리를 형성하기 위해서는 루트노드를 제외한 노드들은 부모 노드가 존재해야한다.

- 만약 부모 노드가 존재하지 않는다면 그 수는 이진트리로 표현할 수 없는 수 이다.

- 문제해서는 중위순회 형태로 수를 표시했기 때문에 이진트리를 형성하는지 확인할 때 중위순회 형태로 찾아가는 방식으로 문제를 해결했다.

 

 

 

<Code>

def binary(num):
    temp = []
    while True:    # 2진수로 변환
        a, b = divmod(num, 2)
        temp.insert(0, b)

        if a != 0:
            num = a
        else:
            break

    res = ''.join(map(str, temp))

    length = len(res)
    cnt = 1    # 이진트리 높이
    while True:    # '0'을 추가하여 이진트리 높이만큼 포화 이진트리가 되도록 글자 수 맞춰주기
        if length > (2 ** cnt - 1):
            cnt += 1
        else:
            break

    ln = 2 ** cnt - 1
    if length != ln:
        res = '0' * (ln - length) + res

    return res


def check(num, now, end):    # 중위 순회(Inorder Traversal)로 이진 트리 확인
    if now == end:    # 해당 노드에 도착한 경우 문자열에서 노드에 해당 하는 값 리턴
        return num[now]

    mid = (now + end) // 2

    # 이미 False 값이 리턴 되었거나 부모가 더미 노드('0) 인데 자식이 더미 노드가 아닌 경우 False 리턴
    left = check(num, now, mid - 1)
    if not left or (num[mid] == '0' and left == '1'):
        return False

    right = check(num, mid + 1, end)
    if not right or (num[mid] == '0' and right == '1'):
        return False

    if num[mid] == '0' and left == '0' and right == '0':    # 부모, 자식 모두가 '0'인 경우는 '0'을 리턴
        return '0'

    return '1'    # 부모, 자식 모두가 '1'인 경우 '1'을 리턴


def solution(numbers):
    answer = []
    for number in numbers:
        bin_num = binary(number)

        if check(bin_num, 0, len(bin_num) - 1):
            answer.append(1)
        else:
            answer.append(0)

    return answer

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.