[백준] 5639 Binary Search Tree

백준 5639 Binary Search Tree

• https://www.acmicpc.net/problem/5639

• Binary Search Tree의 전위 순회 결과값으로 후위 순회 결과값 만들기

Binary Search Tree 구현 풀이

• 이진 탐색 트리를 직접 구현하여 풀이하는 방법

• Naive한 풀이 방식임
  -> 입력값이 전위 순회 결과값이라는 점을 활용하지 못 한다

#include <iostream>
#include <limits.h>
using namespace std;

struct Node {
	int data;
	Node* left;
	Node* right;
};

Node* insertNode (Node* node, int data) {

	if (node == NULL) {
		node = new Node();

		node->data = data;
		node->left = node->right = NULL;

		return node;
	}

	if (data < node->data)
		node->left = insertNode(node->left, data);
	else
		node->right = insertNode(node->right, data);
	
	return node;
}

//트리의 후위 순회
void postorder(Node* root) {
	
	//leftChild
	if (root->left != NULL) postorder(root->left);
	//rightChild
	if (root->right != NULL) postorder(root->right);
	//root
	cout << root->data << '\n';
	
	return;
}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);

	Node* root = NULL;

	int input;
	while (true) {
		cin >> input;
		if (cin.eof() == true) break;

		root = insertNode(root, input);
	}

	postorder(root);
	return 0;
}

⚡ Binary Search Tree 구현 없이 풀이

• 이진 탐색 트리를 직접 구현하지 않고 풀이하는 방법도 있지만, 아직 이해하지 못했다

• 백준 2263 트리의 순회를 풀고 나니 쉽게 풀 수 있었다!

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int preorder[100001] = { 0 };

void postorder(int start, int end) {
	//base case
	if (start > end) return;
	if (start == end) {
		cout << preorder[start] << "\n";
		return;
	}

	//preorder : ROOT + leftChild + rightChild
	int root = preorder[start];

	//이진탐색트리: leftChild는 항상 ROOT보다 작고, rightChild는 항상 ROOT보다 크다
	//고로 ROOT보다 큰 preorder값이 시작되는 지점 = rightChild의 preorder 시작되는 지점
	int rightStart = end + 1;
	for (int i = start + 1; i <= end; ++i) 
		if (root < preorder[i]) {
			rightStart = i;
			break;
		}
	
	//postorder: leftChild + rightChild + ROOT
	postorder(start+1, rightStart - 1);
	postorder(rightStart, end);
	cout << root << "\n";

	return;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int input;
	int index = 0;
	while (true) {
		cin >> input;
		if (cin.eof() == true) break;

		preorder[index++] = input;
	}

	postorder(0, index - 1);
	return 0;
}

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> preorder; 
vector<int> postorder;

//startIdx ~ endIdx 범위 전위순회 -> 후위순회
void solve(int startIdx, int endIdx) {
	//base case
	if (startIdx > endIdx) return;
	if (startIdx == endIdx) {
		postorder.push_back(preorder[startIdx]);
		return;
	}

	int rootIdx = startIdx;
	int rightStartIdx = endIdx + 1;
	for (int i = startIdx + 1; i <= endIdx; ++i) {
		if (preorder[rootIdx] < preorder[i]) {
			rightStartIdx = i;
			break;
		}
	}

	//왼쪽 자식 처리
	solve(rootIdx + 1, rightStartIdx - 1);
	
	//오른쪽 자식 처리
	solve(rightStartIdx, endIdx);

	//루트 처리
	postorder.push_back(preorder[rootIdx]);
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	while (true) {
		int input;
		cin >> input;
		if (cin.eof()) break;

		preorder.push_back(input);
	}
	
	solve(0, preorder.size()-1);

	for (int i = 0; i < postorder.size(); ++i) {
		cout << postorder[i]<<"\n";
	}
	return 0;
}

📌참고자료

• 트리의 순회(전위, 중위, 후위)
  https://withhamit.tistory.com/282

• 백준 5639 Binary Search Tree 풀이
  https://kyunstudio.tistory.com/172

• cin.eof()
  https://lollolzkk.tistory.com/15

알고리즘 문제에서 입력값의 범위가 주어지지 않는 경우:
파일이 종료될때까지 입력을 받으라는 의미 -> cin.eof()를 사용한다

//EOF를 만날때까지 무한 입력
while (true) {    
    	cin >> n;
	if(cin.eof() == true) break;
}

• EOF
  https://www.acmicpc.net/board/view/24867

터미널에서 직접 입력을 넣을 때에는 EOF를 수동으로 넣어주어야 한다

• 윈도우: Ctrl + Z
• UNIX: Ctrl + D
• BOJ에서는 입력을 넣을 때 파일로 주기 때문에 EOF가 붙어 있다