🎲문제

---

주소:백준 5639

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

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

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

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

⌨ 입력

---

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

✅ 풀이

---

풀이방법

전위 순회에서 후위 순위로 전환하는 과정에서 규칙을 찾아 재귀를 활용하여 문제를 풀었다. 루트, 왼쪽, 오른쪽으로 나누어 재귀를 돌리고 요소가 1개일때, 해당요소를 출력한다. 후위순위는 왼쪽, 오른쪽,루트 순서이므로 재귀를 돌린 후 왼쪽, 오른쪽, 루트 순서로 출력하도록 한다.

몰랐던부분은 어디까지 숫자를 받아야 될지 몰라서 당황했는데 파일단위로 생각해서 EOF가 들어올때 까지 계속 숫자를 받는다고 생각하면 된다.

1. EOF가 들어올 때까지 계속 숫자를 입력받는다. 파일단위이기 때문에 입력에 내용이 없더라도 자동으로 끝날때까지 입력받는다.
2. 재귀를 활용해서 풀것이기 때문에 재귀함수를 선언해준다.

void init() {
	while (1) {
		if (scanf("%u", &arr[index]) == EOF) { break;  }
		index++;
	}
}

void solve() {
	recursion(0, index-1);
}

1. 재귀는 루트, 왼쪽, 오른쪽으로 나눌 것이기 때문에 기준을 루트, 오른쪽 끝 인덱스 두 개의 인자를 받는다.(left는 root+1이므로 따로 정하지 않아도 된다.)
2. left와 right 모두 start + 1로 설정한다. left의 시작점은 start+1로 고정이며, right는 루트보다 숫자가 커질 때 right가 시작이므로 while문으로 right의 인덱스를 결정한다.
3. 출력의 순서는 후위순회이므로 왼쪽 오른쪽 루트 순서로 출력한다. 그러므로 순서를 left right root 순서로 함수를 작성한다.
4. left + 1 == right(left가 하나일 경우 더 나눌 수 없음) 인 경우, left를 먼저 출력하고, 더 나눌 수 있는 경우 재귀 함수를 돌린다.
5. 마찬가지로 right == finish(right가 하나일 경우 더 나눌 수 없음)인 경우, right를 두번째로 출력하고, 더 나눌 수 있는 경우 재귀함수를 돌린다.
6. 마지막으로 해당 단계의 root를 출력한다. root는 무조건 원소가 하나이므로 바로 출력하면된다.

void recursion(int start, int finish) {
	int left = start + 1, right = start + 1;
	while (right <= finish ) {
		if (arr[right] > arr[start]) {
			break;
		}
		right++;
	}

	//왼쪽
	if (left + 1 == right)
		cout <<  arr[left] << "\n";
	else if(left < right)
		recursion(left, right-1);
		

	//오른쪽
	if (right == finish)
		cout << arr[right] << "\n";
	else if(right < finish)
		recursion(right, finish);
		

	//루트
	cout << arr[start] << "\n";
}

전체 코드

---

#include<iostream>
#include<algorithm>

using namespace std;

void init();
void solve();
void recursion(int, int);

unsigned int arr[10001]; unsigned int index = 0;

void init() {
	while (1) {
		if (scanf("%u", &arr[index]) == EOF) { break;  }
		index++;
	}
}

void solve() {
	recursion(0, index-1);
}

void recursion(int start, int finish) {
	int left = start + 1, right = start + 1;
	//cout << i << " " << finish << "\n";
	while (right <= finish ) {
		if (arr[right] > arr[start]) {
			break;
		}
		right++;
	}

	//왼쪽
	if (left + 1 == right)
		cout <<  arr[left] << "\n";
	else if(left < right)
		recursion(left, right-1);
		

	//오른쪽
	if (right == finish)
		cout << arr[right] << "\n";
	else if(right < finish)
		recursion(right, finish);
		

	//루트
	cout << arr[start] << "\n";
}

int main() {
	init();
	solve();
	return 0;
}