[BOJ] 5639 이진 검색 트리 (C/C++)

5639번: 이진 검색 트리

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

---

이전에 이런 비슷한 문제를 풀었던 것 같다. 이렇게 어떤 순회의 출력을 주고 다른 순회의 값을 알아냈던 것 같은데 그때는 트리를 만들지는 않았다.

 

이 문제에서는 전위 순회한 입력을 사용해서 트리를 만든다. 어떤 순회였어도 트리를 만들 수 있었을 것이다. 노드 하나 삽입하는 데에 $O(logN)$이 사용되므로 최대 걸릴 수 있는 시간은 $NlogN$이라고 추정할 수 있다. 실제론 처음부터 트리 크기가 N이 아니므로 이것보단 작을 것이다.  트리를 구성한 이후에 출력하는 것은 선형 시간에 가능하므로 충분히 시간 안에 풀 수 있었다.

동적 할당은 이전에 삼성 특강에서 들었던 메모리 풀 방식을 사용했다. new나 malloc을 사용한 다른 정답자들에 비해 빨리 풀 수 있었다. 하지만 이진트리임을 정확히 인지하고 힙처럼 배열을 사용한 사람도 있었다. 그 사람은 나보다도 빨랐다. 노드가 최대 만개이므로 그렇게도 풀 수 있었겠다는 생각과 함께 트리가 skewed면 안되지 않나 의심이 든다. 진짜 재수 없으면 $2^{1}0000$ 개 노드가 필요한 거 아닌가..? 코드를 보니 배열을 100만 개쯤으로 사용하면 모든 테스트 케이스에 대해서 처리할 수 있는 모양이다. 사실 skewed 하게 입력이 들어오면 시간상 내 코드도 안되긴 할 것 같다.

 

	#define _CRT_SECURE_NO_WARNINGS
	#include <stdio.h>
	using namespace std;
	typedef struct _Node {
	int n;
	_Node* left, * right;
	} Node;
	Node nodePool[10001]; int cnt;
	Node* root;
	int num;
	Node* getNode() {
	Node* temp = &nodePool[cnt++];
	temp->n = 0;
	temp->left = NULL;
	temp->right = NULL;
	return temp;
	}
	Node* insert(Node *cur, int n) {
	if (cur == NULL) {
	cur = getNode();
	cur->n = n;
	return cur;
	}
	if (n < cur->n) cur->left = insert(cur->left, n);
	else cur->right = insert(cur->right, n);
	return cur;
	}
	void postorder(Node* cur) {
	if (cur->left) postorder(cur->left);
	if (cur->right) postorder(cur->right);
	printf("%d\n", cur->n);
	}
	int main() {
	while (scanf("%d", &num) != EOF) {
	root = insert(root, num);
	}
	postorder(root);
	return 0;
	}

view raw 5639.cpp hosted with ❤ by GitHub

 

후기)

요새 진짜 정신없다. 21학점 + 연구실 인턴이 슬슬 시동걸린 것 같다. 이젠 매일 백준 못 풀 것 같다. 오늘도 수업 듣고 연구실 갔다오니 벌써 9시가 다 되어간다. 아직 복습도 못 했고 내일까지 과제도 있는데....