https://www.acmicpc.net/problem/1991
풀이 ① - 인접 리스트 + 재귀 함수
인접 리스트 List<Character>[] lists에 트리 저장, 재귀 함수로 트리 순회 구현
1. 아이디어
1) 트리의 노드 연결 정보를 인접 리스트 List<Character>[] lists에 저장
- 각 노드의 Left Child, Right Child 저장
ex)lists[0]: 루트 노드 'A'의 Left Child, Right Child 저장
2) 재귀 함수로 각 트리 순회 구현
- 전위 순회 (Preorder): Parent → Left Child → Right Child
- 중위 순회 (Inorder): Left Child → Parent → Right Child
- 후위 순회 (Postorder): Left Child → Right Child → Parent
char[] tree에 전체 트리(노드들)를 저장하지 않고,
인접 리스트List<Character>[]를 사용한 이유
- 입력 트리의 형태가 "완전 이진 트리"가 아닌, 그냥 이진 트리
- 트리가 최악으로 Unbalance 할 수 있음
- ex) 최악의 경우로 트리가 오른쪽으로만 길게 뻗친 형태 (Right Child 만 존재)인 경우,
char[] tree의index=> 루트[1],[3],[7],[15], ...,[2^26 - 1]- n 최대 노드 개수: 26
- 부모 노드가
[i]이면, Left Child 는[i * 2], Right Child 는[i * 2 + 1])
- 메모리 초과 발생
=> 최대char[] tree의 메모리: (2^26 - 1) x 2 byte = 134,217,726 byte ~= 대략 134 MB >> 128 MB
2. 자료구조
List<Character>[],ArrayList<Character>[]: 각 노드의 Left Child, Right Child 저장
3. 시간 복잡도
-
1개 부모 노드에서 재귀 호출 2번 수행
- 대충 전체 n개 노드에서, 재귀 호출 2번 모두 수행 가정
- 트리 순회 1번 당, O(2 x n)
-
트리 순회 총 3번이므로, 총 시간 복잡도: O(6 x n)
=> n 최대값 대입: 6 x 26 = 156
코드
import java.io.*;
import java.util.*;
public class Main {
static int n; // 이진 트리의 노드 개수
static List<Character>[] lists; // 각 노드의 left, right child 저장
static StringBuilder sb = new StringBuilder(); // 출력 값
static void preorder(char parent) {
List<Character> list = lists[parent - 'A'];
char leftChild = list.get(0);
char rightChild = list.get(1);
// Parent -> Left Child -> Right Child
sb.append(parent);
if (leftChild != '.')
preorder(leftChild);
if (rightChild != '.')
preorder(rightChild);
}
static void inorder(char parent) {
List<Character> list = lists[parent - 'A'];
char leftChild = list.get(0);
char rightChild = list.get(1);
// Left Child -> Parent -> Right Child
if (leftChild != '.')
inorder(leftChild);
sb.append(parent);
if (rightChild != '.')
inorder(rightChild);
}
static void postorder(char parent) {
List<Character> list = lists[parent - 'A'];
char leftChild = list.get(0);
char rightChild = list.get(1);
// Left Child -> Right Child -> Parent
if (leftChild != '.')
postorder(leftChild);
if (rightChild != '.')
postorder(rightChild);
sb.append(parent);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
lists = new ArrayList[n]; // [0 ~ n-1]
for (int i = 0; i < n; i++)
lists[i] = new ArrayList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
char parent = st.nextToken().charAt(0);
char leftChild = st.nextToken().charAt(0);
char rightChild = st.nextToken().charAt(0);
lists[parent - 'A'].add(leftChild);
lists[parent - 'A'].add(rightChild);
}
// 루트 노드 'A' 에서 시작
preorder('A');
sb.append("\n");
inorder('A');
sb.append("\n");
postorder('A');
sb.append("\n");
System.out.println(sb);
}
}풀이 ② - Tree 직접 구현 + 재귀 함수
Tree를 직접 구현하여 트리 저장, 재귀 함수로 트리 순회 구현
1. 아이디어
Tree를 직접 구현
1) 트리 노드 추가
- Left Child 추가
- Right Child 추가
2) 재귀 함수로 각 트리 순회 구현
- 전위 순회 (Preorder): Parent → Left Child → Right Child
- 중위 순회 (Inorder): Left Child → Parent → Right Child
- 후위 순회 (Postorder): Left Child → Right Child → Parent
입력 트리가 이진 트리 형태이고,
입력 노드 연결 정보가 Parent - Left Child - Right Child 의 순서로 주어지므로,
Tree 직접 구현해서 풀이 가능
2. 자료구조
Tree:Node들을 갖는 트리 구현 클래스
3. 시간 복잡도
-
1개 부모 노드에서 재귀 호출 2번 수행
- 대충 전체 n개 노드에서, 재귀 호출 2번 모두 수행 가정
- 트리 순회 1번 당, O(2 x n)
-
트리 순회 총 3번이므로, 총 시간 복잡도: O(6 x n)
=> n 최대값 대입: 6 x 26 = 156
코드
import java.io.*;
import java.util.*;
class Node {
public char data;
public Node leftChild;
public Node rightChild;
public Node(char data) {
this.data = data;
}
}
class Tree {
public Node root;
public int size;
public Tree(Node root) {
this.root = root;
size++;
}
/* 트리에서 parentData 값을 갖는 parent 노드를 찾아서,
leftData 값을 갖는 leftChild 노드 추가 */
public void addLeft(char parentData, char leftData) {
if (root == null) {
root = new Node(parentData); // Root 추가
root.leftChild = new Node(leftData); // Left Child 추가
size += 2;
}
else
addLeft(root, parentData, leftData);
}
public void addLeft(Node node, char parentData, char leftData) {
if (node == null) // 못 찾은 경우
return;
else if (node.data == parentData) { // 찾은 경우
node.leftChild = new Node(leftData);
size++;
}
else {
addLeft(node.leftChild, parentData, leftData);
addLeft(node.rightChild, parentData, leftData);
}
}
/* 트리에서 parentData 값을 갖는 parent 노드를 찾아서,
rightData 값을 갖는 rightChild 노드 추가 */
public void addRight(char parentData, char rightData) {
if (root == null) {
root = new Node(parentData); // Root 추가
root.rightChild = new Node(rightData); // Right Child 추가
size += 2;
}
else
addRight(root, parentData, rightData);
}
public void addRight(Node node, char parentData, char rightData) {
if (node == null) // 못 찾은 경우
return;
else if (node.data == parentData) { // 찾은 경우
node.rightChild = new Node(rightData);
size++;
}
else {
addRight(node.leftChild, parentData, rightData);
addRight(node.rightChild, parentData, rightData);
}
}
public StringBuilder sb;
/* 전위 순회: Parent -> Left Child -> Right Child */
public void preorder(Node parent) {
sb.append(parent.data);
if (parent.leftChild != null)
preorder(parent.leftChild);
if (parent.rightChild != null)
preorder(parent.rightChild);
}
/* 중위 순회: Left Child -> Parent -> Right Child */
public void inorder(Node parent) {
if (parent.leftChild != null)
inorder(parent.leftChild);
sb.append(parent.data);
if (parent.rightChild != null)
inorder(parent.rightChild);
}
/* 후위 순회: Left Child -> Right Child -> Parent */
public void postorder(Node parent) {
if (parent.leftChild != null)
postorder(parent.leftChild);
if (parent.rightChild != null)
postorder(parent.rightChild);
sb.append(parent.data);
}
}
public class Main_Tree_Dev {
static int n; // 이진 트리의 노드 개수
static Tree tree;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
tree = new Tree(new Node('A'));
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
char parentData = st.nextToken().charAt(0);
char leftData = st.nextToken().charAt(0);
char rightData = st.nextToken().charAt(0);
if (leftData != '.')
tree.addLeft(parentData, leftData);
if (rightData != '.')
tree.addRight(parentData, rightData);
}
tree.sb = new StringBuilder();
tree.preorder(tree.root);
tree.sb.append("\n");
tree.inorder(tree.root);
tree.sb.append("\n");
tree.postorder(tree.root);
tree.sb.append("\n");
System.out.println(tree.sb);
}
}
Silver Star