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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150367

파이썬 소스: https://bit.ly/3JhDMFO

 

문제를 설명하는 방식이 좀 헷갈릴 수 있습니다.

루트 노드는 그대로 유지합니다.

저는 문제의 위의 문장이 좀 제일 헷갈리더라구요. 그래서 다른 분들 풀이를 보고 이해했습니다.

헷갈리는 문제 설명을 간단하게 3가지로 요약하면 아래와 같습니다.

1. 자연수 N이 있다. N을 이진법으로 변환한 B를 만들고, B는 문자열로 변환한다.

2. B에서 한글자씩 때서, 포화 이진 트리를 만드는대 글자가 부족할 수 있으니, 포화 이진 트리가 되도록 B의 왼쪽에 0을 임의의 개수로 붙일 수 있고. 이를 B1이라고 한다.

3. B1로 포화 이진 트리를 만들 수 있으면, 1 리턴하고, 만들 수 없으면 0 리턴한다.

 

포화 이진 트리는 영어로 하면 full binary tree 이구요, 쉽게 말하면, 딱 삼각형 모양으로 생긴 이진 트리입니다. 모든 부모 노드가 2개의 자식 노드를 가지고 있고, 모든 리프 노드의 레벨이 같은 노드를 의미합니다. (완전 이진 트리(complete binary tree)와는 다른 트리입니다.)

 

따라서, 위의 3번 B1의 길이는 1이거나, 2**X + 1입니다. (X는 양수)

자연수 N이 2리고 하면, 이전법으로 10 이구요, 포화 이진 트리가 되기 위해서는 왼쪽에 0이 하나 부족 합니다. 010을 가지고 포화 이진 트리를 그릴 수 있는가? 생각해보면, 가능합니다.

루트 노드가 1이 되구요, 왼쪽 자식 노드가 더미 0, 오른쪽 자식 노드가 더미가 아닌 0

이렇게 3개의 노드를 가지는 포화 이진 트리를 만들 수 있습니다.

 

문제를 풀려면 무엇보다 앞서서, 자연수 N을 이진수 문자열로 변환해야 합니다.

b = bin(n)[2:] if len(b) == 1:     if b == '1':         return 1     else:         return 0

함수 bin()을 사용해서 2진수로 변환하구요, 변환된 이진수는 문자열로 리턴됩니다. 이진수로 변환하면 ‘0b’가 붙기 때문에 [2:]를 사용해서 잘라내 줍니다.

길이가 1일 때 예외 처리를 하는 코드입니다. 길이 1이고, b가 ‘1’이면 1 리턴합니다. b가 ‘0’이면 루트 노드가 0이 됨으로, 트리가 존재할 수 없다고 보고, 0을 리턴했습니다.

l, length = 2, 0 while l <= len(b):     l *= 2     length = l - 1 begin0 = ['0'] * (length - len(b)) b = ''.join(begin0) + b

len(b)값에 따라서, 포화 이진 트리를 만들 수 있는 길이가 달라지기 때문에 해당 길이를 계산하는 코드입니다. 예를 들어 b의 길이가 5라면 2 * 2 * 2 -1 해서 7을 구하는 코드입니다. 7-5 하면 2가 되구요, ‘0’이 2개 부족함으로, b의 앞에 ‘00’을 붙여 주겠습니다.

 

앞에서 설명한 B1을 만들었으니, 이제 B1을 가지고 포화 바이너리 트리를 만들 수 있는지 알아보겠습니다.

def check(b: str) -> int:     if len(b) == 1:         return 1     half = len(b) // 2     parent = b[half:half + 1]     left = b[:half]     right = b[half + 1:]     if parent == '0':         if left.find('1') != -1:             return 0         if right.find('1') != -1:             return 0     return check(left) and check(right)

함수 check()는 재귀적으로 호출 되기 때문에, b의 길이가 1이 되면 무조건 1을 리턴할 수 있습니다. 리프 노드의 값은 0도 1도 둘 다 항상 가능하기 때문입니다.

부모노드의 값이 0인지 1인지 알아볼 차례입니다. len(b) // 2로 나눠서, 중간 값을 찾아내서, parent 에 저장합니다.

만약 parent가 0이라면 left, right 모두 0 이어야 합니다. 0값을 가지는 부모 노드 밑에는 자식 노드가 올 수 없기 때문입니다. 따라서, left, right에 1이 있는지 확인하고, 있으면, 리턴값이 -1 이 아니라면, 0을 리턴합니다.

이제 parent는 1이기 때문에, 왼쪽 스트링 left와 오른쪽 스트링 right를 각각 check 함수를 통해서 포화 이진 트리를 구성할 수 있는지 재귀적으로 탐색해 보면 이문제를 풀 수 있습니다.

 

궁금한 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래 참고하세요.

from typing import List def solution(numbers: List[int]):     answer = []     for n in numbers:         answer.append(check_binarytree(n))     return answer def check_binarytree(n: int) -> int:     b = bin(n)[2:]     if len(b) == 1:         if b == '1':             return 1         else:             return 0     l, length = 2, 0     while l <= len(b):         l *= 2         length = l - 1     begin0 = ['0'] * (length - len(b))     b = ''.join(begin0) + b     return check(b) def check(b: str) -> int:     if len(b) == 1:         return 1     half = len(b) // 2     parent = b[half:half + 1]     left = b[:half]     right = b[half + 1:]     if parent == '0':         if left.find('1') != -1:             return 0         if right.find('1') != -1:             return 0     return check(left) and check(right)