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

문제 링크

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

해결 방법

1. 10진수를 이진수로 바꾸기
2. 포화 완전트리에 대한 개념을 이해
3. 포화 이진트리가 만들어 지지 않는 경우를 이해하고 트리를 순회하는 방법에 대해 배워보자
   10진수를 이진수로 바꾸기10진수를 2진수로 바꾸는 방법은 파이썬에서 여러가지 방법이 있지만 다른언어를 사용할 때를 대비하여 (자바스크립트) while문 만으로 구현하였다.

10진수를 이진수로 바꾸기

1. n이 1이 될 때 까지 반복문을 반복한다.
2. n을 계속 2로 나누고 나머지를 array에 저장한다.
3. 반복문을 탈출 후 1을 append 해준 뒤 거꾸로 뒤집는다.

def convertBinary(n):
 a = []
 while 1 < n:
     tmp = n % 2
     a.append(tmp)
     n = n // 2
 a.append(1)
 cnt = 0
 idx = 1
 while True:
     if 2 ** idx - 1 >= len(a):
         cnt = 2 ** idx - 1
         break
     idx += 1
 a.reverse()

 

포화완전 트리에 대한 이해

포화 완전트리에 대한 이해포화 완전트리는 자식노드가 모두 존재하는 대칭을 이루는 트리를 말한다.
노드의 개수는 항상 2 ** level -1의 개수를 갖는다. 여기서 level은 트리의 층을 의미한다.
1층일 땐 1 개 2층일 땐 3개 3층일 땐 7개...
해당 문제의 경우 0은 더미노드로 표현을 하고 1은 실제 표현하는 노드가 된다.

다음은 42를 표현한 경우이다.

42를 포화완전트리 형태로 만들면 0101010으로 표현할 수 있게 되는데 더미노드를 모두 제거하고나면 다음과 같은 형태가 된다.

직접 그린 그림인데.. 이해하는데 도움이 되면 좋겠습니다...

포화 완전트리를 만드는게 중요함으로 파이썬의 zfill을 사용해서 더미노드가 될 부분을 앞의 갯수만큼 0으로 채워준다. 파이썬이 아닌경우엔 for문으로 채워줄 것 같다

cnt = 0
idx = 1
while True:
	if 2 ** idx - 1 >= len(a):
		cnt = 2 ** idx - 1
		break
	idx += 1
a.reverse()
result = "".join(list(map(str,a)))
result = result.zfill(cnt)

이진트리 순회하기

이 부분이 이문제의 핵심이다. 

자식노드가 존재하는데 부모노드가 되는 부분이 0인 경우엔 이진트리로 표현할 수 없기 때문에

1. 부모노드를 탐색
2. 자식 노드 중 1이 있는 경우에 따라 Ture, False 반환

하는 방법을 선택하였다.

def division_search(start, end, arr):
    if start == end: # start와 end의 경우 리프노드를 의미함으로 탐색 종료
        return True # 끝까지 탐색을 완료했음으로 True 반환
    mid = (start + end) // 2
    if arr[mid] == '0': # mid가 0인 경우
        for i in range(start, mid): # left child 탐색
            if arr[i] == '1': # 1 존재하면 False
                return False
        for i in range(mid + 1, end + 1): # right child 탐색
            if arr[i] == '1': # 1 존재하면 False
                return False
    left = division_search(start, mid - 1, arr)
    right = division_search(mid + 1, end, arr)
    return left and right

전체 코드

def convertBinary(n):
    a = []
    while 1 < n:
        tmp = n % 2
        a.append(tmp)
        n = n // 2
    a.append(1)
    cnt = 0
    idx = 1
    while True:
        if 2 ** idx - 1 >= len(a):
            cnt = 2 ** idx - 1
            break
        idx += 1
    a.reverse()
    result = "".join(list(map(str,a)))
    result = result.zfill(cnt)
    return result

def division_search(start, end, arr):
    if start == end:
        return True
    mid = (start + end) // 2
    if arr[mid] == '0':
        for i in range(start, mid):
            if arr[i] == '1':
                return False
        for i in range(mid + 1, end + 1):
            if arr[i] == '1':
                return False
    left = division_search(start, mid - 1, arr)
    right = division_search(mid + 1, end, arr)
    return left and right
    
def solution(numbers):
    answer = []
    for n in numbers:
        # flag = True
        tmp = convertBinary(n)
        arr = list(tmp)
        flag = division_search(0, len(arr) - 1, arr)
        if flag:
            answer.append(1)
        else:
            answer.append(0)
    return answer