백준 5639 - 이진 검색 트리(C++)

문제

전위 순회하는 이진 트리가 주어진다. 이를 통해 후위 순회한 결과를 출력한다.

 

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다.

 

노드의 수는 10,000개 이하이다.

 

예제 입력

50
30
24
5
28
45
98
52
60

 

예제 출력

5
28
24
45
30
60
52
98
50

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

전위 순회라는 말에서 우리는 이것을 분할 정복으로 문제를 풀 수 있다는 것을 눈치챌 수 있다.

 

전위 순회는 (루트)(왼쪽 자식)(오른쪽 자식) 순으로 출력하는 순회 방법으로 맨 처음 출력되는 것이 루트라는 것을 알 수 있다.

 

또한, 이는 이진 트리이기 때문에 루트를 기준으로 왼쪽은 더 작은 값 오른쪽은 더 큰 값이라는 것을 알 수 있다.

 

그래서 루트를 발견하고 왼쪽과 오른쪽을 나누고 다시 왼쪽과 오른쪽을 분할한 뒤 다시 루트를 발견하고 왼쪽과 오른쪽을 구분한 뒤 더 이상 분할할 수 없는 없을 때 해당 부분 문제에서 루트를 출력하면 되는 것이다.

 

이때 후위 순환은 (왼쪽 자식)(오른쪽 자식)(루트) 순으로 출력하기 때문에 재귀를 호출하는 순서를 생각해서 호출하면 된다.

 

코드

#include <iostream>
#include <vector>

int Arr[10001];

void solve(int preS, int preE)
{
	if (preS >= preE)
		return ;
	int root = Arr[preS];
	int left = 0;
	for (int i = preS + 1; i < preE; i++)
	{
		if (Arr[i] > root)
			break ;
		left++;
	}
	int right = preE - left - 1;
	solve(preS + 1, preS + left + 1);
	solve(preS + left + 1, preE);
	std::cout << root << "\n";
}

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int x;
	int i = 0;
	while (std::cin >> x)
	{
		Arr[i] = x;
		i++;
	}
	solve(0, i);
	return 0;
}

 

문제 출처

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

5639번: 이진 검색 트리