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

 

 

문제

문제 설명

 

 

 

풀이

 

[풀이]

 

이 문제는 이진트리로 특정 수를 표현이 가능한지 풀면 되는 문제다.

 

이진트리로 특정 수를 표현하기 위해서는 자식 노드가 1일 때, 부모의 노드가 0이 되면 안되기만 하면 된다.

 

문제는 특정 자식 노드의 부모노드가 0인지 확인을 하기 위해서 어떤 노드가 부모노드 인지를 잘 알아야한다.

 

DFS로 이진트리가 잘 연결되어 있는지 구해도 되지만 처음에 보자마자 부모노드만 잘 정해준다면 제한 된 범위에서 만들어지는 이진트리의 깊이가 깊지 않아 빠르게 구할 수 있다고 생각했다.

 

문제는 부모노드를 구하는 방법인데 맨 아래 1층과 그 부모인 2층을 비교하면

 

왼쪽 자식 노드(1층) = 부모노드 - (2층/2)

오른쪽 자식 노드(1층) = 부모노드 + (2층/2)

과 같이 나타나는 것을 알 수 있다. 이를 활용해 먼저 이진트리의 부모노드가 누구인지 계산하고 표현 가능한 이진트리인지 풀었다.

 

​

[아이디어 정리]

1. 주어진 수를 이진수로 변환한다.
2. 변환한 이진수를 바탕으로 이진수의 특정 값이 1일때, 최상위 부모 노드가 몇인지 구한다. (값이 1이면서 연결된 가장 상위 부모 노드)
3. 최상위 부모노드가 전부 같다면 true, 하나라도 다르면 false

Code

 

 

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

int parents[128];

string bi(long long num)
{
    string returnA="0";
    while (num>0)
    {
        returnA+=to_string(num%2);
        num/=2;
    }
    return returnA;
}

bool canCalc(long long num)
{
    int myParentsNode=1;
    for (int i=1; i<8; i++)
    {
        // 노드 개수가 2^i-1개씩 늘어남
        if (num<pow(2,pow(2,i)-1))
        {
            myParentsNode=pow(2,i)/2;
            break;
        };
    }
    string str=bi(num);
    
    int realMyParents=0;
    vector<int> pvector(myParentsNode*2,0);
    for (int i=1; i<str.length(); i++)
    {
        int node=i;
        if (str[node]=='1')
        {
            while(true)
            {
                if (node==myParentsNode)
                {
                    pvector[i]=node;
                    break;
                }
                else if(str[node]=='1')
                {
                    node=parents[node];
                }
                else
                {
                    pvector[i]=node;
                    break;
                }
            }
        }
    }
    bool flag=false;
    int pppn=0;
    for (int i=0; i<pvector.size(); i++)
    {
        if (pvector[i]>0)
        {
            if (!flag)
            {
                pppn=pvector[i];
                flag=true;
            }
            else
            {
                if (pppn!=pvector[i])
                {
                    return 0;
                }
            }
        }
    }        
    if (str[pppn]=='0')
    {
        return 0;
    }
    return 1;
}

vector<int> solution(vector<long long> numbers) {
    
    int n,nn,nnn;
    for (int i=1; i<8; i++)
    {
        n=pow(2,i);
        nnn=n*2;
        nn=n/2;
        while(n<64)
        {
            parents[n-nn]=n;
            parents[n+nn]=n;
            n+=nnn;
        }
    }    
    vector<int> answer;
    for (int i=0; i<numbers.size(); i++)
    {
        answer.push_back(canCalc(numbers[i]));
    }
    //단순히 부모 노드가 있는지만 확인하면 되는 문제
    return answer;
}

 

---

 

 

다른 사람의 풀이들이 궁금해서 살펴보니 부모노드를 기준으로 자식노드 인덱싱을 잘 하고, 조건을 설정해 DFS로 풀었다.

처음에 부모 노드만 잘 찾으면 빠르게 풀릴 것 같아서 그렇게 풀었는데, 생각보다 조건 정하는게 헷갈렸는데 나도 DFS로 풀껄 그랬나...?

 

프로그래머스