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);
}
}