[2023 KAKAO BLIND RECRUITMENT] 표현 가능한 이진트리

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

프로그래머스

프로그래머스 2023 KAKAO BLIND RECRUITMENT  LEVEL3 표현 가능한 이진트리 문제입니다

 

문제는 주어진 수를 이진수로 만든 후 더미노드를 추가하여 포화 이진트리 형태로 만듭니다

그 포화 이진트리로  이진수가 표현이 가능한 형태라면 1을 아니라면 0을 정답에 저장하여 출력하는 문제입니다

 

문제의 이해

간단한 예시로

3 (주어진 수)

11 (이진수)

011 (포화 이진트리)

이럴 경우 1을 배열에 추가합니다

 

 

9 (주어진 수)

1001(이진수)

0001001(포화 이진트리)

이럴 경우 0을 배열에 추가합니다

6번 노트때문에 포화이진트리로 표현할 수 없다

 

해당 문제를 풀기위해

1. 주어진 수를 2진수로 만들어줍니다

2. 만들어진 2진수를 포화 2진수로 만들어줍니다

3. 표현이 가능한 포화 2진수인지 검사합니다

 

1. 이진수로 만들기

10 진수를 2진수로 만드는 방법은 1이 될 때까지 2로 나누어 나머지가 있다면 1 아니라면 0을 배열에 추가하는 방식으로 배열에 추가해 줍니다

2. 포화 이진수로 만들기

포화 이진수는 높이에 따라 노드의 개수가 정해져 있습니다

높이가 2라면 3 높이가 3이라면 7과 같이 2^(높이)-1의 식을 활용했습니다

3. 검사하기

저는 노드를 좌우로 분할하여 정복하는 형식으로 검사를 진행하였습니다

배열이 Divison이라는 함수에서 좌우로 나누어 재귀를 통해 검사를 진행하였고 체크해야 할 점은

표현이 불가능한 노드인 경우 2를 return 하도록 하였습니다

1. 최하위 자식노드는 자기 값을 return 합니다

2. 자식이 2(표현이 불가능한 노드라고 판단된 경우)를 return한경우 2를 그대로 return 합니다

3. 자식노드가 0 인가 1 인가 => 둘 다 0이라면 상관없지만 1이 하나라도 있을 경우 해당노드가 1이 아니라면 2를 return 하는 방식으로 표현이 가능한 노드인지 아닌지를 확인합니다

4. 2가 리턴된 경우 0을 그 외는 1을 배열에 추가해 줍니다

 

#include <string>
#include <vector>
#include <iterator>
#include <iostream>
#include <cmath>
using namespace std;

int Division(vector<int> binaryNum);

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;

    for (long long n : numbers)
    {
        vector<int> binaryNum;
        while (n >= 1)
        {
            if (n % 2 == 1)
            {
                binaryNum.push_back(1);
            }
            else
            {
                binaryNum.push_back(0);
            }
            n = n / 2;
        }
        int binaryNumsize = binaryNum.size();


        int tempBinaryNumsize = binaryNumsize;
        int top = 0;
        while (tempBinaryNumsize >= 1)
        {
            top++;
            tempBinaryNumsize = tempBinaryNumsize / 2;
        }

        int insuffivalue = pow(2, top) - 1 - binaryNumsize;
        for (int i = 0; i < insuffivalue; i++)
        {
            binaryNum.push_back(0);
        }

        if (binaryNumsize == 0)
        {
            answer.push_back(0);
        }
        else if (Division(binaryNum) == 2)
        {
            answer.push_back(0);
        }
        else
        {
            answer.push_back(1);
        }
    }

    return answer;
}


int Division(vector<int> binaryNum)
{
    if (binaryNum.size() == 1)
    {
        if (binaryNum[0] == 0)
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
    else
    {
        vector<int> leftv(binaryNum.begin(), binaryNum.begin() + ((binaryNum.size() / 2)));
        vector<int> rightv(binaryNum.begin() + ((binaryNum.size() / 2)+1), binaryNum.end());
        int left = Division(leftv);
        int right = Division(rightv);

        if (left == 2 || right == 2)
        {
            return 2;
        }

        if (binaryNum[binaryNum.size() / 2] == 0)
        {
            if (right == 0 && left == 0)
            {
                return 0;
            }
            else
            {
                return 2;
            }
        }
        else if (binaryNum[binaryNum.size() / 2] == 1)
        {
            return 1;
        }
    }
}