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

Problem : 코딩테스트 연습 - 표현 가능한 이진트리 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

Status : Solved

Time : 00:39:20

 

---

 

문제 설명

 

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

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

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의 원소 ≤ 10^15

 

입출력 예

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

 

 

---

 

풀이

트리의 기본 성질을 이해하고, 이를 빠른 시간안에 적용해야 하는 문제였다(제한 시간이 있으므로...) CS 기본 지식을 코딩테스트를 통해 물어보는 듯한 느낌을 받았다.

이진 트리로 나타낼 수 있는 숫자 여부를 판단하므로, 숫자를 이진 트리 형태로 간주하고 탐색하면서 트리의 기본 성질을 위배하지 않는지 따져보면 된다. 이진 트리라고 표현했지만, 문제 조건상 '포화 이진 트리'의 형태가 되어야 한다. 문제에도 언급하고 있기도 하고.

1. 우선 숫자를 포화 이진 트리에 맞는 형식으로 바꾸어 주어야 한다. 포화 이진 트리(Perfect Binary Tree)는 그 특성상 (2의 제곱승 - 1)개의 노드를 가진다. 이 때 필요하다면 부족한 길이만큼 0을 앞에 추가한다. (그래야만 원본 숫자가 바뀌지 않는다.)
2. 탐색은 재귀적으로 시행할 수 있다.
   1. 만약 현재 위치가 리프 노드라면(즉 length가 1이라면) 무조건 참이 된다.
   2. 그렇지 않은 경우, 중간 노드(length // 2)가 루트 노드가 된다. 리프 노드가 아니므로, 다음과 같은 두 가지 경우가 가능하다. 두 가지에 해당되지 않으면 무조건 거짓이 된다.
      1. 모든 노드가 0 혹은 1인 경우 : 이 경우는 서브 트리 전체가 기본 조건을 위배하지 않는다.
      2. 1에 해당하지 않으면서 루트 노드가 1인 경우 : 1에 해당하지 않는다면, 이 서브 트리는 어떠한 자손 노드가 존재할 수 있다. 두 서브트리가 존재하려면 루트 값이 1이어야 한다.
   3. 2를 만족한다면 오른쪽 서브트리와 왼쪽 서브트리에 대해 재귀적으로 탐색하면 된다. 둘 다 참이어야 한다.

이 경우 탐색 전체에는 O(nlogn)의 시간이 소요된다. n은 이때 이진수의 길이이고, 원소 크기는 최대 10^15, 약 2^50이므로 n은 최대 50을 넘지 않는다. 따라서 적은 탐색 시간 내에 이진 트리 표현 여부를 판별할 수 있다.

 

풀이 코드

def search(number) :
    length = len(number)
    if length == 1 or '1' not in number or '0' not in number:
        return True
    
    mid = length // 2
    if number[mid] == '0':
        return False
    
    return search(number[:mid]) and search(number[mid+1:])

def solution(numbers):
    bin_numbers = [ bin(x)[2:] for x in numbers]
    bin_list = [ 2**x - 1 for x in range(50)]
    answer = list()
    for number in bin_numbers :
        length = len(number)
        for num in bin_list :
            if num >= length :
                number = '0'*(num-length) + number
                break
        answer.append(1 if search(number) else 0)
    
    return answer

풀이 완료!