Ceiling Function

Problem link: https://www.acmicpc.net/problem/12767

문제가 영어인 관계로 굳이 다시 한 번 문제를 적어본다.

이 문제는 임의의 수열이 N개 입력될 때, 각 수열을 Binary Tree로 구성한다면, 트리의 모양이 몇 가지가 나올 수 있는지를 묻는 문제이다.

Full binary tree를 생각한다면, 우리는 각 노드의 위치를 숫자로 표현해 줄 수 있다(마치 우선 순위 큐를 직접 구현할 때 처럼)

• 따라서, 각 수열을 BST에 저장하면서 저장된 위치를 함께 기록해주고,
• 완성된 BST를 순회하며 각 노드의 저장 위치를 배열에 저장해준다.
• 구해진 배열 중 같은 것을 헤아려주면 트리의 모양 수를 알 수 있다.

마지막 같은 배열 헤아리기는 set of set을 활용했다.

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int kMaxLayers = 20;

int N;
int K;

struct Node
{
  int number;
  int position;
  Node* left;
  Node* right;
};

Node* Insert(Node** root, const int number, const int position = 1)
{
  if (*root == nullptr)
  {
    *root = new Node();
    (*root)->number = number;
    (*root)->position = position;
    (*root)->left = nullptr;
    (*root)->right = nullptr;
  }
  else
  {
    if ((*root)->number > number)
    {
      (*root)->left = Insert(&((*root)->left), number, (*root)->position * 2);
    }
    else
    {
      (*root)->right = Insert(&((*root)->right), number, (*root)->position * 2 + 1);
    }
  }

  return *root;
}

void DeleteTree(Node* root)
{
  if (root == nullptr)
  {
    return;
  }

  DeleteTree(root->left);
  DeleteTree(root->right);
}

void Traverse(Node* root, set<int>& positions)
{
  if (root == nullptr)
  {
    return;
  }

  positions.insert(root->position);
  Traverse(root->left, positions);
  Traverse(root->right, positions);
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N >> K;

  vector<Node*> trees(N, nullptr);
  for (int it = 0; it < N; ++it)
  {
    for (int jt = 0; jt < K; ++jt)
    {
      int layer;
      cin >> layer;
      trees[it] = Insert(&trees[it], layer);
    }
  }

  // Solve
  set<set<int> > shapes;
  for (int it = 0; it < N; ++it)
  {
    set<int> shape;
    Traverse(trees[it], shape);
    shapes.insert(shape);
  }

  cout << shapes.size() << '\n';

  for (int it = 0; it < N; ++it)
  {
    DeleteTree(trees[it]);
  }

  return 0;
}