문제

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

---

입력

• 트리를 전위 순회한 결과가 주어진다. 모든 값은 한 줄에 하나씩 주어진다.

---

출력

• 입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

---

풀이

제한조건

• 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다.
• 노드의 수는 10,000개 이하이다.
• 같은 키를 가지는 노드는 없다.

접근방법

트리 순회, 재귀

문제를 푸는 방법은 2가지가 있다.

1. 트리 순회
가장 정직한 방법이다.
주어지는 입력을 바탕으로 트리 구조를 구성한 다음
트리 구조에서 부터 후위 순회한 결과를 만들어 가는 방법.

2. 재귀
전위 순회의 결과값을 보고, 재귀적으로 값만 찾아서 후위 순회로 변경하는 방법.

1번 방법의 경우, 코드의 구현량이 많아진다.
알고리즘을 푸는 입장에서 코드의 구현량이 많아진다는 것은 실수 확률 증가와 풀이 시간 증가를 가져오기 때문에 간단한 2번 방법으로 접근해보자.

어떻게 전위 순회 결과를 토대로 후위 순회 결과를 얻을 수 있을까.
우선 조건을 기반으로 생각해보자.

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

노드가 최대 10000개 주어진다. 주어진 입력을 배열에 담아보자.

배열에 담긴 수로 부터 위의 조건을 적용하면 어떤것이 루트이고, 왼쪽, 오른쪽인지 식별이 가능하다.

가장 처음이 Root에 해당하는 수이고, Root보다 큰 수가 나오기 직전까지가 Left, 그 이후가 Right로 구성된다.

이제 Left로 구성된 부분을 다시 살펴보자.

Left로 구성된 부분에서 다시 또 root, left, right를 구할 수 있다.

즉, 처음 입력된 배열에서 부터 재귀적으로 분할해 나가면 V, L, R을 식별할 수 있고,

우리는 V->L->R 순으로 입력 받았던 것을 L->R->V 순으로 출력만 하면 된다.

---

코드

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

public class Main {
	static int[] arr = new int[10001];
	static int count = -1;
	static StringBuilder sb = new StringBuilder();

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

		String s;
		while ((s = in.readLine()) != null) {
			int value = stoi(s);
			count++;
			arr[count] = value;
		}
		print(0, count + 1);
		System.out.println(sb);
	}

	/**
	 * V -> L -> R 의 입력 순서를 L -> R -> V 순서로 변경
	 */
	private static void print(int start, int end) {
		if (start >= end)
			return;

		int v = arr[start];
		int boundary = start + 1;
		for (int i = start + 1; i <= end; ++i) {
			boundary = i;
			if (arr[i] > v)
				break;
		}
		print(start + 1, boundary);
		print(boundary, end);
		sb.append(v).append("\n");
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}