오늘 풀어본 문제는 백준의 5639번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
이 문제의 내용과 조건은 다음과 같다.
이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 $50\ 30\ 24\ 5\ 28\ 45\ 98\ 52\ 60$ 이고, 후위 순회 결과는 $5\ 28\ 24\ 45\ 30\ 60\ 52\ 98\ 50$ 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 $10^6$ 보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 $10,000$ 개 이하이다. 같은 키를 가지는 노드는 없다.
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
이 문제는 이진 검색 트리 (Binary Search Tree, a.k.a. BST) 에서 삽입 과정과 전위 순회를 구현하는 문제이다. 데이터구조 수업 때 배우고 직접 구현했던 자료 구조로, 그냥 그 코드를 긁어와서 조금만 손본 뒤 제출해도 되었겠지만, 다음과 같은 이유로 다시 직접 구현하기로 했다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class BinarySearchTree {
private:
struct Node {
Node* left;
Node* right;
T value;
Node(const T& value) : left(nullptr), right(nullptr), value(value) {}
};
Node* head;
void preOrder(Node* currentNode, std::ostringstream& oss, const char& separator) {
oss << currentNode->value << separator;
if (currentNode->left != nullptr) {
preOrder(currentNode->left, oss, separator);
}
if (currentNode->right != nullptr) {
preOrder(currentNode->right, oss, separator);
}
}
void inOrder(Node* currentNode, std::ostringstream& oss, const char& separator) {
if (currentNode->left != nullptr) {
inOrder(currentNode->left, oss, separator);
}
oss << currentNode->value << separator;
if (currentNode->right != nullptr) {
inOrder(currentNode->right, oss, separator);
}
}
void postOrder(Node* currentNode, std::ostringstream& oss, const char& separator) {
if (currentNode->left != nullptr) {
postOrder(currentNode->left, oss, separator);
}
if (currentNode->right != nullptr) {
postOrder(currentNode->right, oss, separator);
}
oss << currentNode->value << separator;
}
public:
BinarySearchTree() : head(nullptr) {}
~BinarySearchTree() {
if (head != nullptr) {
std::stack<Node*> s;
s.push(head);
while (!s.empty()) {
Node* currentNode = s.top();
s.pop();
if (currentNode->left != nullptr) {
s.push(currentNode->left);
}
if (currentNode->right != nullptr) {
s.push(currentNode->right);
}
delete currentNode;
}
}
}
void insert(const T& value) {
if (head == nullptr) {
head = new Node(value);
}
else {
Node* currentNode = head;
Node* parentNode = nullptr;
while (currentNode != nullptr) {
parentNode = currentNode;
if (value < currentNode->value) {
currentNode = currentNode->left;
}
else {
currentNode = currentNode->right;
}
}
if (value < parentNode->value) {
parentNode->left = new Node(value);
}
else {
parentNode->right = new Node(value);
}
}
}
void remove(const T& value) {
// TODO: Implement this later
}
bool search(const T& value) {
Node* currentNode = head;
while (currentNode != nullptr) {
if (value < currentNode->value) {
currentNode = currentNode->left;
}
else if (value > currentNode->value) {
currentNode = currentNode->right;
}
else {
return true;
}
}
return false;
}
std::string preOrder(const char& separator = ' ') {
std::ostringstream oss;
if (head != nullptr) {
preOrder(head, oss, separator);
}
std::string result = std::move(oss).str();
if (!result.empty()) {
result.pop_back();
}
return result;
}
std::string inOrder(const char& separator = ' ') {
std::ostringstream oss;
if (head != nullptr) {
inOrder(head, oss, separator);
}
std::string result = std::move(oss).str();
if (!result.empty()) {
result.pop_back();
}
return result;
}
std::string postOrder(const char& separator = ' ') {
std::ostringstream oss;
if (head != nullptr) {
postOrder(head, oss, separator);
}
std::string result = std::move(oss).str();
if (!result.empty()) {
result.pop_back();
}
return result;
}
};
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
BinarySearchTree<int> bst;
int number;
while (cin >> number) {
bst.insert(number);
}
cout << bst.postOrder('\n');
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
간만에 데이터구조 과제를 하는 느낌을 받았다. 실제 과제는 구현해야할 것도 많고 필요한 기능을 전부 구현해야 했지만, 이 문제는 삽입과 전위 순회만 필요한 문제여서 삭제같이 구현하기 귀찮은 기능들은 뒤로 미뤄두는 식으로 끝냈기 때문에 금방 끝났다.
내가 구현한 BinarySearchTree
는 여기서2 확인할 수 있다. 나중에 필요하면 BinarySearchTree::remove
함수를 구현해서 업데이트 하도록 하겠다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/5639
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/binary_search_tree.hpp