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

풀이 ①

입력 전위 순회에서 부모 노드를 찾아서 Left Subtree, Right Subtree 로 나눔

1. 아이디어

• 이진 탐색 트리 (Binary Search Tree, BST)

  • Left Subtree 는 모두 부모 노드보다 작음
  • Right Subtree 는 모두 부모 노드보다 큼

• 후위 순회 (Postorder): Left Child → Right Child → Parent

• 입력 preorder 배열에서 루트(부모) 노드를 정하고
  Left Subtree, Right Subtree 에 대해 재귀호출
  
  1) Left Subtree: postorder(startIdx + 1, 부모 노드보다 큰 노드의 idx - 1)
  2) Right Subtree: postorder(부모 노드보다 큰 노드의 idx + 1, endIdx)
  3) 부모 노드 preorder[startIdx] 출력

2. 자료구조

• int[]: 입력, 전위 순회 순서
  => 최대 노드 개수 10^5 개
  => int[10^5]: 4 x 10^5 byte = 0.4 MB

3. 시간 복잡도

• 부모 노드 1개에 대해 재귀 호출 2번 수행

=> 전체 최대 노드 수 10^5에 대해 대략 재귀 호출 2번 수행
=> 총 시간 복잡도: 2 x 10^5 << 1억 (1초)

코드

import java.io.*;

public class Main {
	static final int MAX_COUNT = 10000;
	static int[] preorder = new int[MAX_COUNT];			// 입력: 전위 순회
	static StringBuilder sb = new StringBuilder();		// 출력 값, 후위 순회 저장

	static void postorder(int startIdx, int endIdx) {
		if (startIdx > endIdx)
			return;

		int parent = preorder[startIdx];

		int rightChildIdx;
		for (rightChildIdx = startIdx; rightChildIdx <= endIdx; rightChildIdx++) {
			if (parent < preorder[rightChildIdx])		// Parent < Right Child
				break;
		}

		postorder(startIdx + 1, rightChildIdx - 1);		// Left Subtree
		postorder(rightChildIdx, endIdx);				// Right Subtree
		sb.append(parent).append("\n");					// Parent 출력
	}

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

		int idx = 0;
		while (true) {
			String input = br.readLine();
			if (input == null || input.equals(""))
				break;
			preorder[idx++] = Integer.parseInt(input);
		}

		postorder(0, idx - 1);

		System.out.println(sb);
	}
}

풀이 ②

이진 탐색 트리 BinarySearchTree를 직접 구현

1. 아이디어

• 이진 탐색 트리 (Binary Search Tree, BST)

  • Left Subtree 는 모두 부모 노드보다 작음
  • Right Subtree 는 모두 부모 노드보다 큼

• 이진 탐색 트리(BinarySearchTree)를 직접 구현하여 트리 저장,
  후위 순회를 재귀 함수로 구현

• 입력이 전위 순회 순서로 들어오므로, 부모 노드를 기준으로 트리 저장

• 후위 순회 (Postorder): Left Child → Right Child → Parent

1) 새로 insert 하려는 노드 값 < 부모 노드인 경우

• case 1) 부모 노드의 Left Child 가 없는 경우,
  새로 Left Child 를 생성하여 삽입

• case 2) 부모 노드의 Left Child 가 이미 있는 경우,
  이미 존재하는 Left Child 로 내려가서 다시 비교 및 삽입
  => 재귀 호출
  

2) 새로 insert 하려는 노드 값 > 부모 노드인 경우

• case 1) 부모 노드의 Right Child 가 없는 경우,
  새로 Right Child 를 생성하여 삽입

• case 2) 부모 노드의 Right Child 가 이미 있는 경우,
  이미 존재하는 Right Child 로 내려가서 다시 비교 및 삽입
  => 재귀 호출

2. 자료구조

• BinarySearchTree: 이진 탐색 트리 구현

3. 시간 복잡도

1) 이진 탐색 트리 저장

• BST의 탐색 / 삽입 시간 복잡도: O(H)
  (H: BST 의 높이)

• BST가 완전 이진 트리(균형이 완벽하게 잡힌 이진 트리)인 경우: O(H) = O(log2 n)
  (n: 노드 개수)

• Worst) BST 가 균형이 잡히지 않은 경우 (BST 가 왼쪽 or 오른쪽으로만 길게 뻗은 경우)
  : O(H)
  => H 최대값으로 노드의 개수 10^5 개 대입
  => BST 저장 시간 복잡도: 10^5
  
  

2) 후위 순회 출력

• 부모 노드 1개에 대해 재귀 호출 2번 수행
  => 전체 최대 노드 수 10^5에 대해 대략 재귀 호출 2번 수행
  => 후위 순회 출력 시간 복잡도: 2 x 10^5

=> 전체 시간 복잡도 = BST 저장 후, 후위 순회 출력
= 10^5 + (2 x 10^5) = 3 x 10^5 << 1억 (1초)

코드

import java.io.*;

class Node {
	public int data;			// 부모 노드의 값
	public Node leftChild, rightChild;

	public Node(int data) {
		this.data = data;
		this.leftChild = null;
		this.rightChild = null;
	}
}

class BinarySearchTree {
	public Node root;
	public StringBuilder sb = new StringBuilder();

	public BinarySearchTree(Node root) {
		this.root = root;
	}

	public void insert(int data) {
		// 루트 노드에서부터 삽입할 위치를 재귀 호출로 찾아서, 새로운 노드 삽입
		root = insertBST(root, data);
	}

	private Node insertBST(Node temp, int data) {
		if (temp == null)
			temp = new Node(data);
		else if (temp.data > data)			// Left Subtree
			temp.leftChild = insertBST(temp.leftChild, data);
		else if (temp.data < data)			// Right Subtree
			temp.rightChild = insertBST(temp.rightChild, data);

		return temp;
	}

	public void postorder(Node node) {
		if (node == null)
			return;

		postorder(node.leftChild);				// Left Subtree
		postorder(node.rightChild);				// Right Subtree
		sb.append(node.data).append("\n");		// Parent 출력
	}
}

public class Main_Dev_BST {
	static BinarySearchTree bst;

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

		int rootValue = Integer.parseInt(br.readLine());
		bst = new BinarySearchTree(new Node(rootValue));
		while (true) {
			String input = br.readLine();
			if (input == null || input.equals(""))
				break;

			bst.insert(Integer.parseInt(input));
		}

		bst.postorder(bst.root);
		System.out.println(bst.sb);
	}
}