<Lv.3> 표현 가능한 이진트리 (프로그래머스 : C#)

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

📕 문제 설명

이진트리를 수로 표현하는 방법
1. 이진수를 저장할 빈 문자열 생성
2. 주어진 이진트리에 더미 노드를 추가해 포화 이진트리로 만들기 (루트는 그대로 유지)
3. 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴보기 (노드의 높이는 살펴보는 순서에 영향 x)
4. 살펴본 노드가 더미 노드면 문자열 뒤에 0 추가, 아니면 1 추가
5. 문자열에 저장된 이진수를 십진수로 변환

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

십진수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 여부 반환하기

• Input
  이진트리로 만들고 싶은 수
• Output
  하나의 이진트리로 해당 수를 표현할 수 있는 여부

예제

풀이

1. 십진수를 이진수로 변환한다.
2. 포화 이진트리 상태로 만들어준다.

포화 이진트리는 모든 레벨에 노드가 꽉차있는 이진트리를 의미한다. 따라서 트리의 height에 따른 노드 개수는 다음과 같이 계산 된다.

height = 1 , 노드 1개
height = 2, 노드 3개 (1 + 2)
height = 3, 노드 7개 (1 + 2 + 4)
..
height = n, (2^0 + 2^1 + .. + 2^(n-1))

현재 주어진 숫자의 이진수를 구성하는 문자의 개수가 노드 개수이다. 해당 노드 개수가 포화 이진트리에 해당하는지 확인하고, 부족한 개수만큼 앞에 더미노드 (0)을 붙여준다.

3. 이진트리가 성립되는지 확인 후 정답을 갱신해준다.
주어진 이진수에 대해 DFS로 타고 가면서 이진트리의 여부를 확인한다. (현재 부모가 0인데 자식에 1이 존재하면 false, 모든 노드가 제대로 이루어져있다면 true)

using System;

public class Solution {
    long[] numbers;
    public int[] solution(long[] numbers) {
        this.numbers = numbers;
        int[] answer = new int[numbers.Length];
        
        for (int i = 0; i < numbers.Length; i++)
        {
            string convertedBinary = Convert.ToString(numbers[i], 2); // 1. 10진수 -> 2진수
            int height = 0;
            double temp = 1;
            // 2. 포화 이진트리로 만들기
            // height => 노드 개수 : 2^0 + .. + 2^(height-1)
            while (convertedBinary.Length > temp)
            {
                height += 1;
                temp += Math.Pow(2, height); 
            }
            // 앞에 0 붙이기
            convertedBinary = new String('0', (int)temp - convertedBinary.Length) + convertedBinary;
        
            if (IsValid(convertedBinary)) answer[i] = 1;
        }
        
        return answer;
    }
    
    public bool IsValid(string number)
    {
        bool isValid = true;
        
        int mid = (number.Length - 1) / 2;
        char root = number[mid];
        string left = number.Substring(0, mid);
        string right = number.Substring(mid + 1, mid);
        
        // 부모가 0인데 자식 중 하나가 1이면 이진트리 성립 x
        if(root == '0' && (left[(left.Length - 1) / 2] == '1' || right[(right.Length - 1) / 2] =='1'))
        {
			return false;
		}
        
        // 트리 타고 가면서 이진 트리 가능한지 확인하기 
        if(left.Length >= 3) 
        {
			isValid = IsValid(left);
			if(isValid) isValid = IsValid(right);
		}
        
		return isValid;
    }
}

결과