BaekJoon 5639번: 이진 검색 트리

문제는 그닥 어렵지 않았으나 입력을 처리하는 것이 상당히 어려웠던 문제이다.

EOF에 대해서 잘 모르고 있었기에 시간이 걸렸으며 런 타임 에러와 싸우다 겨우 성공해 낸 문제이다.

 

풀이법

1) 이진 검색 트리의 경우 root 값을 잡은 후 root를 기준으로 큰 지 작은 지 비교하면 쉽게 풀 수 있다.

2) 재귀를 이용해서 구현하면 더욱 쉽게 풀 수 있을 것이다.

3) EOF에 대한 개념은 한번 쯤 봐두는 것이 좋을 듯 싶다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <stack>
#include <math.h>
using namespace std;

int n;
struct node {
	int left;
	int right;
};
vector<int> vec;
node arr[1000001];
int rot = -1;
void makeTree(int root, int num)
{
	if (num < root)
	{
		if (arr[root].left == 0)
		{
			arr[root].left = num;
			return;
		}
		root = arr[root].left;
		makeTree(root, num);
	}
	else if(root < num)
	{
		if (arr[root].right == 0)
		{
			arr[root].right = num;
			return;
		}
		root = arr[root].right;
		makeTree(root, num);
	}
}

void post(int root)
{
	if (root == 0)
		return;
	post(arr[root].left);
	post(arr[root].right);
	cout << root << "\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int num;
	while (cin>>num)
	{	
		if (rot == -1)
			rot = num;
		if (num==EOF)
			break;
		makeTree(rot, num);
	}
	post(rot);
}

한계점 및 개선사항

문제를 꼼꼼하게 보지 않아서 배열의 최대 Index를 벗어나는 실수가 있었다. 이는 곧 런타임 에러로 드러 났다. 고칠 수 있어서 다행이었지만 추후에는 이런 문제가 발생하지 않도록 Index 범위를 널널하게 잡아야 겠다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest