❓문제설명

문제 : 백준 5639번 이진 검색 트리
난이도 : 골드 5

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

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 출력하면 되는 문제입니다.

🎯문제 해결 방법

주어진 예시 트리에서 루트 노드 50의 왼쪽 서브트리에 있는 노드들을 살펴보겠습니다.

입력으로 주어졌을 때 50 보다 작으면 전부 왼쪽 서브트리가 되는 것을 확인할 수 있습니다.

50 보다 커지는 순간은 오른쪽 서브트리가 되는 것이죠. 이 성질을 이용을 하면 문제가 풀리게 됩니다!

while(cin >> n){
	v.push_back(n);
}
go(0, v.size());

먼저 입력으로는 입력이 더 이상 주어지지 않을 때 까지 받기위해 이처럼 작성합니다.

void go(int st, int en){
	if(st >= en) return;
	if(st == en-1){
		cout << v[st] << '\n';
		return;
	}
	int idx = st + 1;
	while(idx < en){
		if(v[st] < v[idx]) break;
		idx++;
	}
	go(st+1, idx);
	go(idx, en);
	cout << v[st] << '\n';
	return;
}

다음으로 st는 0, en은 입력받은 크기를 시작으로 go 함수를 시작합니다.

전위 순회한 결과의 특징을 이용해서 기준이 되는 부분을 st의 값이 가리키는 값보다 커질 때로 찾아줍니다.

💻전체 코드

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

int n;
vector<int> v;

void go(int st, int en){
	if(st >= en) return;
	if(st == en-1){
		cout << v[st] << '\n';
		return;
	}
	int idx = st + 1;
	while(idx < en){
		if(v[st] < v[idx]) break;
		idx++;
	}
	go(st+1, idx);
	go(idx, en);
	cout << v[st] << '\n';
	return;
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	while(cin >> n){
		v.push_back(n);
	}
	go(0, v.size());
	return 0;
}