[C++] 백준 9934번: 완전 이진 트리

문제

난이도 : 실버 1
백준 9934번 : 베르트랑 공준

코드

#include <bits/stdc++.h>

using namespace std;

int K;
vector<int> v;
vector<int> answer[10];

void Func(int left, int right, int level)
{
    int mid = (left + right) / 2;
    answer[level].push_back(v[mid]);

    if (left >= right)
    {
        return;
    }

    Func(left, mid - 1, level + 1);
    Func(mid + 1, right, level + 1);
}



int main()
{
    cin >> K;

    for (int i = 0; i < pow(2, K) - 1; i++)
    {
        int input;
        cin >> input;
        v.push_back(input);
    }

    Func(0, v.size() - 1, 0);

    for (int i = 0; i < K; i++)
    {
        for (int node : answer[i])
        {
            cout << node << ' ';
        }
        cout << '\n';
    }
   
    return 0;
}

설명

이진완전트리를 중위순회하는 문제인데 방문한 순서를 기반으로 트리가 어떻게 생겼는지 구해야 하는 문제이다.
내가 생각한 해결 방법은 배열에다가 방문 순서를 담은 후 이진 탐색처럼 mid에 있는 값을 보면 해당 레벨의 노드를 알 수 있다.
예를 들어 1 6 4 3 5 2 7의 mid는 3이고 3을 기준으로 양쪽을 나누어 mid를 보면 6, 2 이런식으로 규칙이 보이기때문이다.
그래서 이진 탐색 구현하는 것처럼 재귀함수를 만들었고 매개변수로 level을 두어 mid값을 answer[level]에 저장하게 해서 끝난 후 출력하도록 했다.

결과