[백준] 5639. 이진 검색 트리 - 실버1

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

5639번: 이진 검색 트리

 

문제 요약

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

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

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

 

문제 해결 아이디어

진짜 오래 걸렸다......

제일 먼저 시도했던 방법은 1. 전위 순회한 결과로 트리를 만든다 2. 후위 순회를 한다 였다.

Node 클래스를 만들었고 입력되는 값마다 현재 노드의 key와 비교해서 left에 넣고 right에 넣고... 하지만 이 또한 재귀가 필요했다. 재귀에 약한 나는 결국 실패했다.

그래서 다음으로 생각했던 방법은 전위 순회한 결과 자체를 배열에 넣어 index를 왔다갔다 하면서 후위 순회를 해 본다는 것이었다.

전위 순회는 루트를 먼저 방문하고 왼쪽, 오른쪽 서브트리를 방문하기 때문에 문제 조건대로라면 루트보다 큰 값을 만나면 그 앞까지는 왼쪽 서브트리라는 것이 된다.

따라서 루트, 즉 현재 노드보다 큰 값이 나올 때까지 배열을 탐색하고 큰 값이 나온다면 그 전까지의 배열을 가지고 재귀를 해 주고, 그 이후의 배열을 가지고 재귀를 돌려 주면 된다.

후위순회는 루트를 제일 마지막에 순회하는 것이기 때문에 재귀가 다 끝난 다음에 루트를 출력해 준다.

 

완성된 코드

package week3;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_BOJ_5639_이진검색트리 {

	/**
	 896ms
	 */
	static int tree[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		tree = new int[10001];

		String str = br.readLine();
		int root = Integer.parseInt(str);
		int index = 0;
		tree[index] = root;
		while ((str = br.readLine()) != null) {
			int input = Integer.parseInt(str);
			tree[++index] = input;
		}
		postOrder(0, index);
	} // end of main

	// 왼쪽은 무조건 작고 오른쪽은 무조건 크다
	// 왼쪽트리와 오른쪽트리의 중간을 찾아야 함 -> 자기보다 큰 원소를 만나기 전까지
	public static void postOrder(int current, int lastIndex) {
		// 기저조건은 current가 lastIndex를 넘어버리면?
		if (current > lastIndex)
			return;

		int base = current + 1;
		while (current <= lastIndex && tree[current] > tree[base] && base <= lastIndex)
			base++;

		// 찾았으면 그 앞의 배열, 즉 왼쪽 트리 안에서 또 후위순회
		postOrder(current + 1, base - 1);
		// 남은 오른쪽 안에서 후위순회
		postOrder(base, lastIndex);
		
		System.out.println(tree[current]);
	}
}