[c++] BOJ 18240 :: 이진 탐색 트리 복원하기

난이도 : 골드 2

문제

이진 탐색 트리 복원하기 문제 바로가기

1부터 N까지의 모든 정수를 한 번씩 포함하고 있는 수열 A1, A2, ..., AN이 있다.

값이 A1인 노드를 루트로 하는 트리에 A2, A3, ..., AN 을 순서대로 삽입하려 한다.

N-1개의 노드를 삽입할 때마다 루트에서 그 노드에 도달하기 위해 거쳐야 하는 간선의 수, 즉 노드의 깊이가 주어질 때 A1, A2, ..., AN을 구하는 프로그램을 작성하시오.

풀이

• 값 받으면서 2N(n-1)<N(n) 인지 체크
  • N(x) : x level의 노드 수
  • 맞으면 트리 생성 불가이므로 -1 반환
  • 왼쪽 포화 이진 트리 생성 (index 이용)
• 중위순회하면서 result[index]에 value 저장
• result 순서대로 출력

코드

#include <iostream>
#include <vector>

using namespace std;

struct Node {
   int index;
   vector<Node*> children;

   Node(int idx) {
      index = idx;
   }
};

vector<vector<Node*>> tree(300001, vector<Node*>());
int result[300001];


int idx = 1;
void Inorder(Node* head) {
   if (head->children.size() > 0) {
      // 왼쪽 자식 존재
      Inorder(head->children[0]);
   }
   result[head->index] = idx++;
   if (head->children.size() > 1) {
      // 오른쪽 자식 존재
      Inorder(head->children[1]);
   }
}

int main() {
   // 노드의 깊이(depth)는 2^depth개 만큼만 나올 수 있다
   // 1. 값 받으면서 2N(n-1)<N(n) 인지 체크 => 맞으면 트리 생성 불가 -1
   // 2. 왼쪽 포화 이진 트리 생성 (index 이용, value 빈 값)
   // 3. 중위순회로 value 채우기 => 채우면서 result[index]에 value 저장
   // 4. result 순서대로 출력

   int N; cin >> N;

   int index = 0;
   Node* head = new Node(++index);

   tree[0].push_back(head);

   for (int i = 0; i < N - 1; i++) {
      int level; cin >> level;

      Node* tmp = new Node(++index);

      int insertIdx = tree[level].size();
      if (tree[level - 1].size() < (insertIdx / 2) + 1) {
         cout << -1;
         return 0; // 정상 종료
      }
      tree[level].push_back(tmp);
      tree[level - 1][insertIdx/2]->children.push_back(tmp);
   }

   Inorder(head);

   for (int i = 1; i <= N; i++) {
      cout << result[i] << " ";
   }
}

개선

코드가 길다길어..

결과

아이디	메모리	시간	코드 길이
gmldms784	52212	248	1423