[백준] 이진 검색 트리(5639)

문제

[백준] 이진 검색 트리

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

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

사진이 첨부되어 있으니 링크를 통해 문제를 확인해주세요.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

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

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

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

해설

이전에 풀이한 트리의 순회(2263) 문제와 비슷한 유형의 문제이다.

BST(이진 검색 트리)의 특징을 잘 알고 있다면 어렵지 않게 풀이할 수 있다고 생각된다. 문제에 나와 있듯이 세 가지 조건을 만족하는 이진 트리가 이진 검색 트리이며, 주어진 전위 순회 결과를 통해 알 수 있는 것은 가장 첫 번째 노드가 루트 노드라는 것이다.

전위 순회 결과를 탐색하면서 기준값인 루트 노드보다 큰 값을 발견하면 그 위치를 기준으로 왼쪽 자신과 오른쪽 자식을 나누고, 이를 재귀 함수를 통해 반복해주며 후위 순회 결과를 구할 수 있다.

런타임에러를 겪는 어려움이 있었는데, 이건 입력에서 발생한 오류였다. while((str = br.readLine()) != null)일 때, NullPointerException이 발생하였고, 빈 값("")이 입력으로 들어 왔을 때 while문이 true가 되는 것을 발견하였다. 그래서 (str.length() > 0) 조건을 추가하였고 드디어 런타임에러에서 벗어날 수 있었다.

풀이

import java.util.*;
import java.io.*;

public class Main {
	static List<Integer> preorder;
	static int[] postorder;
	static int index;

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

		preorder = new ArrayList<>();

		String str = "";

		while ((str = br.readLine()) != null && str.length() > 0) {    //EOF까지 입력받음
			preorder.add(Integer.parseInt(str));
        }

		postorder = new int[preorder.size()];

		index = preorder.size() - 1;
		getPostOrder(0, preorder.size() - 1);

		StringBuilder sb = new StringBuilder();

		for (int num : postorder) {
			sb.append(num).append("\n");
		}

		System.out.println(sb.toString());
	}

	public static void getPostOrder(int start, int end) {
		if (start <= end) {
			postorder[index--] = preorder.get(start);

			int i, count = 0;
			for (i = start + 1; i <= end; i++) {
				if (preorder.get(start) <= preorder.get(i))
					break;

				count++;
			}

			getPostOrder(start + count + 1, end);
			getPostOrder(start + 1, start + count);// 왼쪽
		}
	}
}