프로그래머스 표현 가능한 이진트리 (포화이진트리)

이진트리는 아는데, 이진트리, 삼진트리, 균형트리까지는 구현해본 적 있어서 이거 쉬운 문제 아니냐? 하고 클릭했는데 포화이진트리... 개념이 이해가 안간다. 문제를 읽어도 이해가 안가서 결국 검색...

• 포화이진트리. 그냥 다 채운 이진트리다.
• 다 채워서 트리를 만들었는데 링크가 끊어지느냐?를 묻는 문제같다.
• 1, 3(+2), 7(+4), 15(+8), ...
• 대충 가즈아!

문제 설명

당신은 이진트리를 수로 표현하는 것을 좋아합니다.

이진트리를 수로 표현하는 방법은 다음과 같습니다.

1. 이진수를 저장할 빈 문자열을 생성합니다.
2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
5. 문자열에 저장된 이진수를 십진수로 변환합니다.

이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.

다음은 이진트리를 수로 표현하는 예시입니다.

주어진 이진트리는 다음과 같습니다.

주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.

노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.

당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.

이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ numbers의 길이 ≤ 10,000
  • 1 ≤ numbers의 원소 ≤ 1015

입출력 예

numbers	result
[7, 42, 5]	[1, 1, 0]
[63, 111, 95]	[1, 1, 0]

입출력 예 설명

입출력 예 #1

7은 다음과 같은 이진트리로 표현할 수 있습니다.

42는 다음과 같은 이진트리로 표현할 수 있습니다.

5는 이진트리로 표현할 수 없습니다.

따라서, [1, 0]을 return 하면 됩니다.

입출력 예 #2

63은 다음과 같은 이진트리로 표현할 수 있습니다.

111은 다음과 같은 이진트리로 표현할 수 있습니다.

95는 이진트리로 표현할 수 없습니다.

따라서, [1, 1, 0]을 return 하면 됩니다.

풀이

• 테케는 되는데... 채점하면 실패 + 런타임 에러

import math

def check_tree(s):
    l_s = len(s)
    if l_s == 1:
        return s
    else:
        center = l_s//2
        if s[center] == '1':
            return check_tree(s[:center]) + s[center] + check_tree(s[center+1:])
        else:
            return '0' * len(s)
    
def solution(numbers):
    answer = []
    for n in numbers:
        s = bin(n)[2:]
        l = len(s)
        h = int(math.log2(l+1) + 0.5) #노드가 n일때 포화이진 트리의 최소높이는... log2(n+1)
        new_l = 2 ** h - 1 #포화 시키려면 n이 몇개 필요한가...
        
        tree = []
        for i in range(new_l - l): #중심으로 어디로 맞춰야 하는가? 케이스가 몇개?
            s = s + "0"
        tree.append(s)
        for i in range(new_l - l):
            s = s[-1:]+s[:-1]
            tree.append(s)
        
        _tmp = 0
        for t in tree:
            if t == check_tree(t):
                _tmp = 1
                break
        answer.append(_tmp)
    return answer
    

테스트 1
입력값 〉	[7, 42, 5]
기댓값 〉	[1, 1, 0]
실행 결과 〉	테스트를 통과하였습니다.

테스트 2
입력값 〉	[63, 111, 95]
기댓값 〉	[1, 1, 0]
실행 결과 〉	테스트를 통과하였습니다.

• 이럴 땐 재귀호출 리미트를 해제해본다.
  • 실패
    • 트리의 모양이 아닌거야?
      • 중심을 맞출 필요 없이... 그냥 앞에 0만 추가해서 칸 채우고 실행하면 되는건가?
      • 글쿤 뒤에 0을 추가하면 다른 수가 되는구나!!! 
        • 노 상관...
          • 실패...
            • 어찌해야 하나.. .실패
              • 조금 바꿔봐.. 실패...
• 문제를 다시 읽어보도록 하자 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
  • 모르겠는데???
• 문자열 자르는 부분 인덱스 에러 나는거 찾았고...
  • 어차피 답은 실패

import math
import sys
limit_number = 15000
sys.setrecursionlimit(limit_number)

def check_tree(s):
    l_s = len(s)
    if l_s == 1:
        return s
    else:
        center = l_s//2
        if s[center] == '1':
            return check_tree(s[:center]) + s[center] + check_tree(s[-center:])
        else:
            return '0' * l_s
    
def solution(numbers):
    answer = []
    
    for n in numbers:
        s = bin(n)[2:]
        l = len(s)
        h = math.floor(math.log2(l+1) + 0.5) #노드가 n일때 포화이진 트리의 최소높이는... log2(n+1)
        new_l = 2**h - 1 #포화 시키려면 n이 몇개 필요한가...
        ss = '0' * (new_l-l) + s
        
        if ss == check_tree(ss):
            answer.append(1)
        else:
            answer.append(0)
        
    return answer

• 아... 고쳤다.
  • 어쩐지... 아무렇게나 갖다쓴 최소 트리 높이 공식이 문제였다.
    • h = int((math.log2(l+1)) + 0.5) # 틀림
    • h = int(math.log2(l)) + 1 # 이게 맞음
• 통과...
  • 난 문자열로 만들어서 비교하는 방식으로 짰는데,
  • 다른 사람들은 대부분 값 비교해서 True, False 반환하는 걸로 짰다.

import math
    
def solution(numbers):
    answer = []

    def check_tree(s):
        l_s = len(s)
        if l_s <= 1:
            return s
        else:
            center = l_s//2
            if s[center] == '1':
                return check_tree(s[:center]) + s[center] + check_tree(s[-center:])
            else:
                return '0' * l_s
            
    for n in numbers:
        s = bin(n)[2:]
        l = len(s)
        h = int(math.log2(l)) + 1
        new_l = 2**h - 1
        ss = '0' * (new_l-l) + s
        
        if ss == check_tree(ss):
            answer.append(1)
        else:
            answer.append(0)
        
    return answer

• 속도는 별로 안 좋은 줄 알았는데 (별로 나쁘지 않다? 다른 분들 거보다 빠른 경우도 있고)

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.4MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.05ms, 10.3MB)
테스트 4 〉	통과 (0.13ms, 10.3MB)
테스트 5 〉	통과 (0.25ms, 10.3MB)
테스트 6 〉	통과 (0.50ms, 10.3MB)
테스트 7 〉	통과 (0.74ms, 10.1MB)
테스트 8 〉	통과 (0.59ms, 10.3MB)
테스트 9 〉	통과 (3.42ms, 10.3MB)
테스트 10 〉	통과 (29.76ms, 11MB)
테스트 11 〉	통과 (35.81ms, 11.3MB)
테스트 12 〉	통과 (32.86ms, 11.1MB)
테스트 13 〉	통과 (35.53ms, 11MB)
테스트 14 〉	통과 (28.53ms, 11MB)
테스트 15 〉	통과 (20.11ms, 10.7MB)
테스트 16 〉	통과 (46.41ms, 11.2MB)
테스트 17 〉	통과 (66.56ms, 11.2MB)
테스트 18 〉	통과 (43.63ms, 11.2MB)
테스트 19 〉	통과 (33.30ms, 10.9MB)
테스트 20 〉	통과 (24.01ms, 10.8MB)

• 고수의 풀이.
  • 라인 짧은 건 속도 비슷하거나 느리고,
  • 라인이 길면 가독성이 안좋아서 그냥 내 코드로 만족하는 걸로...
    • 가독성 좋은 코드

import sys
sys.setrecursionlimit(100000000)
def solution(numbers):
    # 이진 수를 저장할 빈 문자열을 생성한다
    # 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만든다
    # 만들어진  포ㅏ 이진트릐의 노드들을 가장 왼쪽 노부터 가장 오른쪽 노드까지 왼쪽에 있는 순서대로 살펴본다
    # 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니면 1을 추가합니다.
    # 문자열에 저장된 이진수를 십진수로 변환합니다.

    # 포화 이진트리 
    # n이 주어질 때, 
    # 트리의 높이... 
    heights = [0] * 6

    for i in range(1,7) :
        heights[i-1] = 2 ** i - 1

    def convert(n) :
        n = bin(n)[2:]
        m = len(n)
        h = 0
        for height in heights :
            if height >= m :
                h = height
                break

        # 해당 서브 트리가 성립하느냐 성립하지 않느냐
        def check(num) :
            if len(num) == 1 :
                return True
            mid = len(num) // 2
            # 서브트리의 루트노드가 더미노드라면
            # 그 아래의 노드들은 전부 더미노드여야 한다.
            # 왼쪽 자식의 성립여부
            left = check(num[:mid])
            # 오른쪽 자식의 성립여부
            right = check(num[mid+1:])
            if num[mid] == '0' :
                l = num[:mid]
                r = num[mid+1:]
                return l[mid//2] == '0' and r[mid//2] == '0' and left and right
            # 더미 노드가 아니라면
            else :
                return left and right

        return check(n.zfill(h))

    return list(map(lambda x : int(convert(x)),numbers))
    
정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.04ms, 10.3MB)
테스트 3 〉	통과 (0.06ms, 10.1MB)
테스트 4 〉	통과 (0.33ms, 10.4MB)
테스트 5 〉	통과 (0.39ms, 10.2MB)
테스트 6 〉	통과 (1.33ms, 10.2MB)
테스트 7 〉	통과 (2.15ms, 10.3MB)
테스트 8 〉	통과 (0.70ms, 10.1MB)
테스트 9 〉	통과 (6.97ms, 10.3MB)
테스트 10 〉	통과 (60.65ms, 11.1MB)
테스트 11 〉	통과 (67.44ms, 11.2MB)
테스트 12 〉	통과 (64.22ms, 11.3MB)
테스트 13 〉	통과 (65.08ms, 11.1MB)
테스트 14 〉	통과 (53.55ms, 10.9MB)
테스트 15 〉	통과 (42.54ms, 10.9MB)
테스트 16 〉	통과 (152.05ms, 11.3MB)
테스트 17 〉	통과 (131.74ms, 11.1MB)
테스트 18 〉	통과 (119.02ms, 10.9MB)
테스트 19 〉	통과 (124.56ms, 11.1MB)
테스트 20 〉	통과 (69.30ms, 10.5MB)

• 대부분 문자열로 만들어서 비교 안하고, 그냥 값을 비교해서 바로 False 던지는 방식을 사용한다.
  • 생각해보니 False 던지는거나 '0' * len(s) 던지는거나 같다.
  • 그리고 10의 15승을 2진수로 해봤자 몇 글자 안되니까, 그냥 문자열로 다시 넘기고 비교해도 문제 없다고 판단됨.
•  내 코드 최종.

import math

def check_tree(s):
    l_s = len(s)
    if l_s <= 1:
        return s
    center = l_s//2
    if s[center] == '1':
        return check_tree(s[:center]) + s[center] + check_tree(s[-center:])
    else:
        return '0' * l_s

def solution(numbers):
    answer = []
            
    for n in numbers:
        s = bin(n)[2:]
        l = len(s)
        new_l = 2**(int(math.log2(l)) + 1) - 1
        s = '0' * (new_l-l) + s
        if s == check_tree(s):
            answer.append(1)
        else:
            answer.append(0)
        
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.4MB)
테스트 2 〉	통과 (0.04ms, 10.2MB)
테스트 3 〉	통과 (0.04ms, 10.1MB)
테스트 4 〉	통과 (0.13ms, 10MB)
테스트 5 〉	통과 (0.43ms, 10.3MB)
테스트 6 〉	통과 (0.76ms, 10.1MB)
테스트 7 〉	통과 (1.36ms, 10.4MB)
테스트 8 〉	통과 (0.61ms, 10.2MB)
테스트 9 〉	통과 (4.10ms, 10.1MB)
테스트 10 〉	통과 (33.47ms, 10.9MB)
테스트 11 〉	통과 (38.04ms, 11.3MB)
테스트 12 〉	통과 (32.66ms, 11.2MB)
테스트 13 〉	통과 (52.37ms, 11.1MB)
테스트 14 〉	통과 (49.03ms, 11.2MB)
테스트 15 〉	통과 (22.16ms, 10.7MB)
테스트 16 〉	통과 (64.52ms, 11.3MB)
테스트 17 〉	통과 (54.35ms, 11.2MB)
테스트 18 〉	통과 (64.12ms, 11.2MB)
테스트 19 〉	통과 (48.87ms, 10.9MB)
테스트 20 〉	통과 (20.43ms, 10.8MB)