9934_완전 이진 트리

Concept & Idea

간단히 재귀함수로 구현할 수 있는 문제였다. 
완전 이진 트리이기 때문에 입력은 당연히 2^k-1만큼 들어올것이다.

전체 리스트의 left, right의 중간 지점 녀석이 현재 depth의 루트인 녀석이다. 
재귀함수를 구현할 때, 가장 먼저 해야할 점은 해당 함수의 인자와 종료 조건을 결정하는 것이다.

종료조건은 보통의 이진탐색 로직의 모습과 거의 유사하다.
그 이후엔 어떤 순서로 이 함수를 다시 호출할지 적어주면 된다.
이 문제에서는 트리의 출력이 좌측부터이기 때문에 그냥 왼쪽부터 재귀하도록 구현했다.  

Code

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> result[10], input;
void make_tree(int depth, int left, int right){
    if (left>right)
        return;
    if (left == right) {
        result[depth].push_back(input[left]);
        return;
    }
    int mid = (left+right)/2;
    result[depth].push_back(input[mid]);
    make_tree(depth+1, left, mid-1);
    make_tree(depth+1, mid+1, right);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int k;
    cin>>k;
    int length = pow(2, k)-1;
    for(int i=0; i<length; i++) {
        int num;
        cin>>num;
        input.push_back(num);
    }
    make_tree(0, 0, length-1);
    for(int i=0; i<k; i++) {
        int result_size = result[i].size();
        for(int j=0; j<result_size; j++) {
            if(j==result_size-1)
                cout<<result[i][j];
            else
                cout<<result[i][j]<<" ";
        }
        cout<<"\n";
    }
}

 

Fealing

변수를 전역으로 두는 습관을 좀 줄여야하는데,, 알고리즘 풀때는 만능인걸 어쩌지 😃

벡터나 리스트, 맵같은 데이터를 통째로 함수 인자로 안넘기고 싶은 나의 마음이랄까.. 👀
그래도 아주 깔끔하게 풀어서 만족!

좀더 빨리 생각을 정리해서 풀수 있으면 좋으련만.. 꾸준히 다시 풀어야지 뭐,,