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

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

프로그래머스

 

문제 분석

문제에서 요구하는 것은 주어진 숫자를 이진수로 바꾸고 포화 이진트리로 나타냈을 때 해당 트리가 이진트리가 맞는지를 판별하는 것이다.

이진수를 포화 이진트리로 나타내려면 앞에 0을 채워서 값을 가공해줘야 한다. 이 부분을 좀 더 분석해보도록 하자.

아래와 같이 생긴 것이 포화 이진트리이다. 리프노드를 제외하고 모두 2개의 자식노드를 가지고 있는 것을 포화 이진트리라고 한다.

 

1층짜리 포화 이진트리라면 노드의 수는 1개, 2층이면 3개, 3층이면 7개이다. 즉 N층짜리 포화 이진트리의 노드 개수는 2^N - 1개이다.

그렇기 때문에 만약 7을 이진수로 바꿔 1011을 도출해냈다면 0001011로 바꾸어 7자리로 맞춰줘야한다. 이렇게 구한 수열로 이진트리가 성립되는지를 판단하면 된다.

이진트리의 정의는 자식 노드의 개수가 최대 2인 트리이다. 즉 아래와 같이 편향된 트리도 이진트리이다.

그리고 문제에 나온 포화 이진트리는 완전 이진트리와 혼동하기 쉬운데 차이점은 아래와 같다. 즉 포화 이진트리는 완전 이진트리에 포함되는 개념이다.

아이디어

문제 풀이 과정은 크게 두 부분으로 나뉜다.
1. 주어진 수를 이진수로 바꾸기. 이때 포화 이진트리 노드의 개수에 맞춰 값을 보정해줘야 한다.
2. 이진수 수열을 보고 해당 수열로 이진트리가 성립되는지를 판단한다.

이진수를 구하는 공식은 아래와 같다.

출처: https://dojang.io/mod/page/view.php?id=1760

이렇게 나머지들을 거꾸로 모으면 이진수가 된다. 일반적으로 이진수를 구하는 코드는 아래와 같이 작성한다.

while(num!=0){
        st+=to_string(num%2);
        num/=2;
    }
reverse(st.begin(),st.end());

그래서 st에는 1011이 들어갔다가 뒤집으며 13의 이진수인 1101이 생성된다. 그렇기에 0을 추가하여 자릿수를 맞추고 싶으면 뒤집기 전에 0을 추가하면 된다.

1011 > 1011000 > 0001101

이제 이진트리가 성립되는지 판단할 방법에 대해 알아보자. 이진트리는 앞서 봤듯이 자식의 개수가 최대 2개인 트리이다. 즉 자식이 0개, 1개, 2개여도 된다. 그런데 이 문제에서는 포화 이진트리를 만들고, 0인 노드는 없는 노드로 치기 때문에 자식이 2개가 넘어갈 경우는 없다. 그렇기에 중간에 끊어졌는지(0의 자식중에 1이 있는지)만 검사하면 된다.

나는 이 부분을 check함수를 통해 구현했는데 작동 방식은 예시를 통해 살펴보도록 하겠다.

아래와 같이 주황색부분이 비어있다고 가정해보자. 이 경우 끊어진 부분이 있기 때문에 이진트리가 성립하지 않는다.

1011111이라는 수열이 주어졌을 때 check함수는 해당 수열을 왼쪽, 가운데, 오른쪽으로 분리한다.

왼쪽: 101
가운데: 1
오른쪽: 111

그리고 가운데가 1이면 왼쪽과 오른쪽 서브트리에 대해 재귀적으로 이진트리를 성립하는지 검사하고, 0이라면 자식들이 모두 없는지(0인지)를 검사한다.

위 예제의 경우 가운데가 1이니 왼쪽과 오른쪽 서브트리를 검사하려고 할 것이다.

왼쪽 서브트리를 다시 쪼개면 아래와 같이 된다.

왼쪽: 1
가운데: 0
오른쪽: 1

가운데가 0이니 자식들이 모두 0인지를 검사한다. 자식들이 모두 0이라면 수열 자체가 0이여야하니 인자로 받은 수열(101)을 순회하며 모두 0인지 검사한다. 그런데 인자로 받은 수열(101)에는 1이 포함되어있으니 이진트리를 성립하지 않는다고 판별하게 된다.

중요한 것은 인자로 들어온 수열의 길이가 1이면 재귀호출을 중단하는 것이다. 수열의 길이가 1이라는 것은 리프노드까지 도달했다는 뜻이고, 리프노드는 자식이 없기 때문에 루트가 1이든, 0이든 이진트리 조건을 만족한다.

모두 이해했다면 다음 부분으로 넘어가도 되지만 이해가 안된 부분이 있다면 아래 예제도 보도록 하자. 이번 예제는 이진트리를 성립하는 경우이다. 

처음에는 아래와 같이 쪼개질 것이다.

왼쪽: 111
가운데: 1
오른쪽: 011

여기서도 가운데가 1이니 왼쪽과 오른쪽에 대해 이진트리 여부를 판별한다.

왼쪽에 대해 이진트리를 판별하면 아래와 같다.

왼쪽: 1
가운데: 1
오른쪽: 1

가운데가 1이니 재귀적으로 왼쪽(그림의 4번노드)과 오른쪽(그림의 5번 노드) 서브트리에 대해 이진트리 여부를 검사하고, 해당 노드들은 리프노드이니 재귀호출을 중단한다.

이제 오른쪽 서브트리(3,6,7번 노드들)에 대해 이진트리 여부를 판별하게 된다. 그러면 아래와 같이 쪼개지게 된다.

왼쪽: 0
가운데: 1
오른쪽: 1

가운데 노드가 1이니 왼쪽과 오른쪽에 대해 재귀적으로 이진트리 여부를 판별하게 되고 해당 노드들 역시 리프 노드이니 재귀호출이 중단된다.

모든 재귀호출이 중단될 때 까지 이진트리가 아니라는 결과가 나온 적이 없기 때문에 해당 수열은 이진트리를 만족한다고 볼 수 있다.

코드

전체 코드는 아래와 같다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

bool isPossible;

string toBinary(long long num){
    string st="";
    while(num!=0){
        st+=to_string(num%2);
        num/=2;
    }

    long long full = floor(log2(st.size()))+1; // 포화 이진트리 층 구하기

    for(int i=st.size();i<pow(2,full);i++){  // 포화 이진트리 노드 수 맞추기 위해 0추가
        st+='0';
    }
    reverse(st.begin(),st.end());
    return st;
}

void check(string binary){  //포화이진트리를 나타내는 문자열이 이진트리를 성립하는지 확인
    if(!isPossible||binary.size()==1)return;
    char middle = binary[binary.size()/2];
    string left = binary.substr(0,binary.size()/2);
    string right=binary.substr(binary.size()/2+1,binary.size()/2);

    if(middle=='0'){ //만약 가운데 숫자가 0이면(루트가 0이면), 양 옆의 숫자도 0이여야 함. 만약 루트가 0인데 자식이 있다면 끊어진 것
        for(auto c:binary){
            if(c!='0'){
                isPossible=false;
                return;
            }
        }
    }else{ //가운데 숫자가 1이면(루트가 1이면), 좌우 서브트리에 대해 검사
        check(left); 
        check(right);
    }
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for(auto num:numbers){
        isPossible=true;
        string binary=toBinary(num);
        check(binary);
        
        isPossible?answer.push_back(1):answer.push_back(0);
    }
    return answer;
}