[Programmers]프로그래머스 표현 가능한 이진트리 문제풀이

이진트리개념, 전위순회, 트리가 형성되는지 판단하는 능력 등이 필요

 

#include <string>
#include <vector>
#include<iostream>
#include<cmath>
using namespace std;
/*
<문제>
이진트리를 십진수로 표현하고자 함
주어진 이진트리에 더미노드를 더해서 포화되도록 만듬
해당트리 전위순회하면서 더미노드는 0, 아니면 1 기록
해당 수 십진수로 변경하는 거
 => 정수가 주어졌을 때, 이걸 이진트리로 만들 수 있는지를 판단해야함
 
<입력> - 각 원소는 10^15 이하 자연수 - 2진수로 최대 52자리
numbers[~10000] 이진트리로 만들고 싶은 정수배열
 
<출력>
result[~10000] 표현가능 시 1, 아니면 0 담기
 
<예시>
numbers            result
[7, 42, 5]        [1, 1, 0]
[63, 111, 95]    [1, 1, 0]
 
<풀이>
이진수 자리가 2^N - 1자리면, N층으로 트리 표현
배열로 2진수 나열했을 때, 루트는 정 가운데임(항상 홀수 개의 배열)
 
트리 조건
1. 루트 자리에 0이 들어가면 안됨 - 2번에 포함될 수도
2. 루트를 제외한 모든 노드는 부모가 있음
 
부모를 어떻게 찾는지?
전체 N층 트리일 때, i층 노드의 왼쪽자식은 i-2^(i-1), 오른쪽자식은 i+임
 
전체 자리수 : n -> n은 2의 제곱수 - 1
트리의 전체 층(floor) : log(n+1)
루트 위치 : n/2
 
1. 자연수를 이진수 배열로 저장(vector<int> num)
2. 부모를 저장하는 parent[]배열 선언해서 이용 - O(N)
 - parent[n/2]=-1   //없는거
 - i=2 (depth이고, 한층 내려갈수록 1 증가 / floor보다 커지면 함수 종료 )
 - parent[n/2-(2^(floor-i))= n/2, parent[n/2+(2^(floor-i))= n/2
   (자식 찾아가서 부모 저장)
 - 이거 재귀로 구현(자식의 num값이 1일때만)
3. num 순차탐색하며, 1인 경우 해당 인덱스로 parent찾아가서 0 아니면 계속 탐색, 0이면 0 저장
4. 모두 탐색 후, 1인 노드가 모두 부모가 존재할 경우(루트제외) 1 담기
 
*/
 
void setParent(int n, int floor, vector<int>& parent, int cur_node, int depth, vector<int> num) {
    if (depth > floor) return;  //종료조건(현재 층이 전체층보다 아래를 가리킬 때)
    int leftchild = cur_node - pow(2, (floor - depth)), rightchild = cur_node + pow(2, (floor - depth));
    
    parent[leftchild] = cur_node; parent[rightchild] = cur_node;
    if (num[leftchild] == 1) setParent(n, floor, parent, leftchild, depth + 1, num);
    if (num[rightchild] == 1) setParent(n, floor, parent, rightchild, depth + 1, num);
}
 
vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
   
    for (int ii = 0; ii < numbers.size(); ii++) {   //numbers 반복
        long long number = numbers[ii];   //현재 루트에서의 번호
        int n = 0;  //전체 자리수   / '0'은 48, '1'은 49
        int floor = 0;
        vector<int>num; //이진수 변환한 값 저장할거
        vector<int>parent;  //num의 각 자리의 부모위치저장
        int totalN = 1; //n의 총 자리수
 
        long long tmp = number;
        while (tmp != 0) { //자리수 계산
            tmp >>= 1; n++;
        }//자리수 계산 끝 -> 2^i - 1 형태로 변환해야함
 
        
        while (totalN - 1 < n) {
            totalN <<= 1;   floor++;    //floor도 같이 계산
        }
        totalN--;
        //totalN 계산완료
 
        
        for (int i = totalN - 1; i >= 0; --i) {
            num.push_back(number >> i & 1);
            parent.push_back(-1);   //부모 일단 없는걸로
        } 
        //totalN자리까지 나타냄, num 저장완료
 
        int root = totalN / 2;
        if (num[root] == 0) { answer.push_back(0); continue; }  //root가 0인경우
 
        setParent(totalN, floor, parent, root, 2, num);   //부모 설정완료
 
        //이제 num탐색하면서 모두 부모 존재하는지 확인할거
        bool flag = true;   //표현가능여부
        for (int i = 0; i < num.size(); i++) {
            if (i == root) continue;    //root인 경우는 예외
            if (num[i] == 1 && parent[i] == -1) {
                flag = false; break;
            }
        }
        if (flag == true) answer.push_back(1);
        else answer.push_back(0);
 
    }
    return answer;
}
 
int main(){
    int c; cin >> c;
    vector<long long> num;
    while (c--) {
 
        int a; cin >> a;
        num.push_back(a);
    }  
    vector<int>ans = solution(num);
 
    for (int i = 0; i < ans.size(); i++) 
        cout << ans[i] << " ";
    return 0;
}