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

문제

• 이진트리를 수로 표현하기
      1. 이진수를 저장할 빈 문자열 생성
      2. 주어진 이진트리에 더미 노드 추가해 포화 이진트리 만들기
      3. 가장 왼쪽 노드부터 오른쪽 노드까지 왼족 순서대로 살피기
          왼쪽 -> 루트 -> 오른쪽 순으로 보기
      4. 더미 노드면 문자열에 0 추가, 아니면 1 추가
      5. 문자열에 저장된 이진수를 십진수로 변환하기
      => 이 십진수는 이진트리로 표현 가능한 수
• 1 <= (number 길이) <= 10,000
  1 <= (number 원소) <= $10^{15}$
• 숫자를 이진트리로 표현할 수 있다면 1, 없다면 0을 담아 리턴하기

 

풀이

• 시간 복잡도 : number 길이가 10,000 이므로 각 숫자에 대한 판단을 4천번 연산 안에 해결해야 함
  • -> 복잡한 알고리즘은 아닐 것. 쉽게 찾는 방법이 있을 것
• 이진트리로 표현 가능한 수 : 중심 노드가 0이 아닌 경우
  • 각 중심 노드 위치는 정 중앙
  • 하지만 모두 다 더미 노드라면 중심 노드가 0이어도 된다.
• 최대 숫자가 $10e15$이므로 전체 트리의 높이는 6이다.
  • 즉, 전체 노드 개수가 최대 63개

 

def check(bin_num):
    root = len(bin_num)//2      # 중심 노드 위치
    if root == 0 :              # 길이가 1인 문자열은 리턴 (리프 노드)
        return True
    # 중심 노드가 0이면 자식 노드가 모두 0이어야 함
    if bin_num[root] == '0' :   
        if '1' not in bin_num:  
            return True
        return False
    
    # 왼쪽 / 오른쪽 자식 확인하기
    return check(bin_num[:root]) and check(bin_num[root+1:])


def solution(numbers):
    answer = []
    cbts = [1, 3, 7, 15, 31, 63]
    for number in numbers:
        bin_num = str(bin(number))[2:]  # 이진수
        length = len(bin_num)           # 이진수의 길이

        for cbt in cbts :
            if length == cbt :          # 완전 포화 트리 길이인 경우
                break
            elif length < cbt :         # 완전 포화 트리 길이로 만들기
                bin_num = "0"*(cbt-length) + bin_num
                length = cbt
                break
        answer.append(1 if check(bin_num) else 0 )

    return answer

 

References

• 프로그래머스 Lv3