[PGM] # 2023 KAKAO BLIND RECRUITMENT 표현 가능한 이진트리 (Python)[PGM] # 2023 KAKAO BLIND RECRUITMENT Representable Binary Tree (Python)
📅
🚀
알고리즘 분류 🔗
재귀, 이진트리
🚀
문제 설명 🔗
0 또는 양의 정수가 주어집니다. 이 수를 이진수로 변환 후 이진 트리에 대입 시, 이진 트리가 온전한 지 확인하는 문제입니다.
예를 들어, 9를 이진수로 변환하면 1001이 됩니다. 이진 트리에 대입하면 다음과 같습니다.
1
\
0
/ \
0 1
1 0 0 1
이 트리는
온전하지 못한 트리
입니다. 이 문제에서는 0이 있는 경우 해당 노드는 비어있는 노드로 취급합니다. 다음 예시는 7을 이진수로 변환한 후 이진 트리에 대입한 모습입니다. 1
/ \
1 1
1 1 1
이 트리는 빈 노드를 가지는 자식 노드가 없으므로
온전한 트리
입니다. 이처럼 온전한 트리이면 1, 아니면 0을 리스트로 반환하는 문제입니다.🚀
풀이 🔗
- 주어진 수를 이진수로 변환합니다.
- 이진수의 길이를 구한 후, 들어갈 이진 트리의 높이를 구합니다. (2의 n승이 이진수의 길이보다 크거나 같을 때까지 n을 증가시킵니다.)
- 이진수의 길이가 2의 n승이 되도록 0을 채웁니다.
- 이진 트리가 온전한 지 확인하는 함수를 작성합니다.
- 이진 트리가 온전한 지 확인하는 함수는 다음과 같습니다.
- 리스트의 길이가 0이면 True를 반환합니다.
- 리스트의 중간 값이 0이어서 빈 노드이지만 자식 노드에 1이 있는 경우 False를 반환합니다.
- 그렇지 않으면, 리스트의 앞부분과 뒷부분을 재귀적으로 확인합니다. (좌측 자식 노드와 우측 자식 노드를 확인합니다.)
- 주어진 수들에 대해 이진 트리가 온전한 지 확인한 결과를 리스트에 담아 반환합니다.
🚀
코드 - Python 🔗
def solution(numbers):
answer = []
for s in numbers:
binnum, height = bin(s)[2:], 0 # 주어진 수를 이진수로 변환
while 2 ** height <= len(binnum): # 이진수의 길이가 2의 n승이 되도록 높이를 구함
height += 1
binnum = binnum.zfill(2 ** height - 1) # 이진수의 길이가 2의 n승이 되도록 0을 채움
answer.append(1 if check(binnum) else 0 )
return answer
def check(lst): # 이진 트리가 온전한 지 확인하는 함수
n = len(lst) // 2
if n == 0: # 리스트의 길이가 1이면 True
return True
elif lst[n] == "0" and ("1" in lst): # 빈 노드이지만 자식 노드에 1이 있는 경우 False
return False
else:
return check(lst[:n]) and check(lst[n + 1:]) # 재귀적으로 확인🚀
핵심 🔗
- 이진 트리의 높이를 구하는 방법
- 이진 트리가 온전한 지 확인하는 방법(자식 노드를 재귀적으로 확인)