프로그래머스, 표현 가능한 이진 트리

프로그래머스, 표현 가능한 이진 트리

 

🪴 문제 

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

프로그래머스

 

🪴 분류 

accepted

 

🪴 풀이

10진수를 2진수로 바꾼뒤.

포화 이진 트리의 갯수만큼 맞춰 더미 노드를 채워줬다.

이진 트리의 레벨에 따른 포화 이진트리 갯수는 그림을 그리며 규칙을 찾았다.

level1 : 노드 1개

level2 : 노드 3개

level3 : 노드 7개

level4 : 노드 15개

leveln : 노드 2의 n승 -1 개

그리고 해당 함수가 포화 이진트리가 될 수 있는지 살펴보면 된다.

 

❌ 잘못된 접근

        flag = True
        # 각 홀수 번째 위치가 루트이고
        # 만약 홀수번째 위치 왼쪽, 오른쪽에 자식노드가 있으면 루트노드 무조건 있어야한다.
        for i in range(1, len(tree)-1, 2):
            if tree[i-1] == '1' or tree[i+1] == '1':
                if tree[i] == '0':
                    flag = False
                    break

처음에는 루트가 될 수 있는 홀수번째 index를 기준으로 자식노드만 있으면 되는줄 알았다.

하지만, 이런 코드로 제출하면 테스트 케이스 5~7, 9~15, 17 번이 불통했다.

 

우리가 이진트리 가능 여부를 살펴볼때처럼 최상위 루트, 왼쪽 서브 루트, 오른쪽 서브 루트를 차례로 살펴보는 방식으로 탐색해야 하는 문제다.

 

✅ 올바른 접근

        # 이분 탐색 왼쪽 서브 노드와 오른쪽 서브 노드
        flag = True
        queue = deque([(0, len(tree)-1)])
        
        while queue:
            left, right = queue.popleft()
            
            if left == right:
                continue
                
            center = (left + right) // 2
            if tree[center] == '0' and '1' in tree[left:right+1]:
                flag = False
                break
            
            queue.extend([(left, center-1), (center+1, right)])

노드가 0이면 그에 대한 왼쪽 서브 자식노드, 오른쪽 서브 자식노드 모두 더미 노드여야 한다.

 

📜 제출 코드

from collections import deque

# 테스트 케이스 추가 [128] -> [1]
def solution(numbers):
    answer = []
    # 십진수를 2진수(bin)로 표시
    # 트리는 2**level - 1개의 노드를 가짐.
    for num in numbers:
        # print(bin(num)[2:], len(bin(num)[2:]))
        
        # 무슨 레벨에 속하는지 살펴보자.
        level = 1
        while(True):
            if len(bin(num)[2:]) <= 2**level-1:
                break
            level += 1
            
        tree = "0" * ((2**level-1) - len(bin(num)[2:])) + (bin(num)[2:])
        # print(new_num)
        root = len(tree) // 2 # 최상위 루트
        
        if tree[root] == '0':
            answer.append(0)
            continue
        
        # 이분 탐색 왼쪽 서브 노드와 오른쪽 서브 노드
        flag = True
        queue = deque([(0, len(tree)-1)])
        
        while queue:
            left, right = queue.popleft()
            
            if left == right:
                continue
                
            center = (left + right) // 2
            if tree[center] == '0' and '1' in tree[left:right+1]:
                flag = False
                break
            
            queue.extend([(left, center-1), (center+1, right)])
                    
        if flag:
            answer.append(1)
        else:
            answer.append(0)
    return answer