[백준] 5639번 : 이진 검색 트리 [C/C++]

#문제

5639번: 이진 검색 트리

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

5639번: 이진 검색 트리

 

---

#접근방법

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

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

이진 검색 트리를 전위 순회한 값이 입력값으로 들어올 때, 후위 순회한 결과를 출력해야 한다.

 

전위 순회는 루트 노드, 왼쪽 트리, 오른쪽 트리 순으로 탐색을 한다.

 

후위 순회는 왼쪽 트리, 오른쪽 트리, 루트 노드 순으로 탐색을 하므로

 

전위 순회한 결과를 왼쪽 트리, 오른쪽 트리로 분할 하여 탐색을 하는 기법인 분할정복을 사용하여 풀면 답을 구할 수 있다.

반응형

---

#풀이

#include <stdio.h>

int arr[10005];
int i;

void post(int start, int end){
	if(start>=end) return;
	
	for(i=start+1;i<end;i++)
		if(arr[start]<arr[i]) break;
	
	post(start+1,i);
	post(i,end);
	printf("%d\n",arr[start]);
	
	return;
}

int main(){
	int n = 0,x;
	
	while(scanf("%d",&x)!=EOF)
		arr[n++] = x;
	
	post(0,n);
	
	return 0;
}

 

입력이 몇 개나 들어올지 모르기 때문에 파일의 끝까지 입력을 받기 위해 조건문에 EOF가 나올 때 까지 입력을 받아주었다.

 

이진 검색 트리에서 루트값보다 작은 값은 왼쪽 서브트리, 루트값보다 큰 값은 오른쪽 서브트리이므로

start+1 ~ end까지 반복문을 돌면서 arr[start]<arr[i]을 만족할 때, start+1 ~ i-1은 왼쪽 서브트리의 범위이고,

i ~ end-1은 오른쪽 서브트리의 범위가 된다.

 

post(start+1,i)과 post(i,end)를 순서대로 호출하면 왼쪽 서브트리, 오른쪽 서브트리를 순차적으로 탐색하게 된다.

 

탐색을 한 후, arr[start]값을 출력시켜주면 후위 순회의 결과를 얻을 수 있다.

 

---

#성능

---

#정리

파일 끝까지 입력을 받을 때 EOF까지 받는다는 사실,

 

전위 순회의 결과는 루트, 왼쪽 서브트리, 오른쪽 서브트리 순으로 탐색을 한다는 사실에서 왼쪽 서브트리와 오른쪽 서브트리로 분할정복하면 후위 순회의 결과를 구할 수 있다는 사실,

 

이를 구현할 수 있는 구현력을 갖춘다면 풀 수 있는 문제였다.