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

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

5639번: 이진 검색 트리

---

문제

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

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

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

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

입력

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

출력

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

728x90

 

예제 입력 1

50
30
24
5
28
45
98
52
60

예제 출력 1

5
28
24
45
30
60
52
98
50

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	
	static ArrayList<Integer> tree;
	static int[] result;
	static int index;
	
	private static void postOrder(int start, int end) { // 후위 순회
		
		result[index--] = tree.get(start); // 시작 노드를 답 배열에 담아줌
		
		int left = -1; // 왼쪽 자식의 노드를 가리킬 인덱스
		int right = -1; // 오른쪽 자식의 노드를 가리킬 인덱스
		
		// 왼쪽 자식의 인덱스 구하기
		if(start + 1 < tree.size() && tree.get(start) > tree.get(start + 1)) { // 왼쪽 자식이 있다면
			left = start + 1; // start의 바로 다음 값은 start 값보다 작을 것
		}
		
		// 오른쪽 자식의 인덱스 구하기
		for (int i = start + 1; i <= end; i++) {
			if(tree.get(start) < tree.get(i)) {// 처음으로 나온 start 값보다 큰 곳이 오른쪽 자식의 인덱스
				right = i;
				break;
			}
		}
		
		// 오른쪽 서브 트리를 후위 순회
		if(right != -1) { // 오른쪽 자식이 있다면
			postOrder(right, end);
		}
		
		// 왼쪽 서브 트리를 후위 순회
		if(left != -1) { // 왼쪽 자식이 있다면
			// 왼쪽 서브 트리의 끝 인덱스는
			// 오른쪽 서브 트리가 있으면 오른쪽 인덱스 - 1
			// 오른쪽 서브 트리가 없으면 끝까지
			postOrder(left, right != -1 ? right - 1 : end);
		}
	}

	public static void main(String[] args){
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		tree = new ArrayList<>(); // 전위 순회한 트리 담을 리스트
		
		while(true) { // 입력이 없을 때까지 반복(입력 끝났으면 ctrl+z)
			try {
				tree.add(Integer.parseInt(br.readLine()));
			}
			catch(Exception e) {
				break;
			}
		}
		
		// 트리를 후위 순회한 결과를 담을 배열
		result = new int[tree.size()];
		index = tree.size() - 1;
		
		// 후위 순회
		postOrder(0, tree.size() - 1);
		
		// 값 출력
		for (int n : result) {
			sb.append(n + "\n");
		}
		System.out.println(sb);
	}
}

트리 구현하기

속도는 많이 느리다.

위의 코드 속도:  392 ms

밑의 코드 속도: 1436 ms

 

위의 코드는 BufferedReader를 사용해 입력을 받았고, 밑의 코드는 Scanner를 사용해 입력을 받아서 입력에서도 속도가 굉장히 많이 차이가 났을 것이다.

import java.io.InputStreamReader;
import java.util.Scanner;

class Node {
	int key;
	Node parent;
	Node leftChild;
	Node rightChild;
	
	Node(int key, Node parent) {
		this.key = key;
		this.parent = parent;
		this.leftChild = null;
		this.rightChild = null;
	}
}

public class Main {

	public static void main(String[] args) throws Exception{

		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		Node root = new Node(sc.nextInt(), null); // 루트 노드 입력
		
		while(sc.hasNext()) { // 입력이 없을 때까지 반복(입력 끝났으면 ctrl+z)
			
			Node p = root; // 현재 가리키고 있는 노드(맨 처음은 언제나 루트 노드를 가리킴)
			int n = sc.nextInt();
			
			while(true) { // 노드를 넣어줄 위치를 찾을 때까지 반복
				
				if(p.key > n) { // 현재 가리키고 있는 노드의 key보다 작을 경우
					
					if(p.leftChild != null) // 왼쪽 노드가 이미 있다면
						p = p.leftChild; // 왼쪽 노드를 가리켜줌
					
					else { // 왼쪽 노드가 비었다면
						p.leftChild = new Node(n, p); // 왼쪽 노드에 넣어주고
						break; // 다음 노드 입력 받으러
					}
				}
				
				else { // 현재 가리키고 있는 노드의 key보다 클 경우

					if(p.rightChild != null) // 오른쪽 노드가 이미 있다면
						p = p.rightChild; // 오른쪽 노드를 가리켜줌
					
					else { // 오른쪽 노드가 비었다면
						p.rightChild = new Node(n, p); // 오른쪽 노드에 넣어주고
						break; // 다음 노드 입력 받으러
					}
				}
			}
		}
		
		// 후위 순회
		Node p = root; // 현재 가리키는 노드
		while(true) {
			if(p.leftChild != null) // 현재 가리키는 노드의 왼쪽 자식이 있다면
				p = p.leftChild; // 왼쪽 자식을 가리킴
			
			else if(p.rightChild != null) // 현재 가리키는 노드의 오른쪽 자식이 있다면
				p = p.rightChild; // 오른쪽 자식을 가리킴
			
			else { // 현재 가리키는 노드의 자식이 없다면
				sb.append(p.key + "\n"); // 출력
				
				if(p.parent == null) // 루트 노드라면
					break; // 모든 출력 완료, 반복문 탈출
				
				if(p.key < p.parent.key) // 자신이 부모 노드의 왼쪽 자식이면
					p.parent.leftChild = null; // 부모 노드의 왼쪽 자식 삭제
				else // 자신이 부모 노드의 오른쪽 자식이면
					p.parent.rightChild = null; // 부모 노드의 오른쪽 자식 삭제
				
				p = p.parent; // 부모 노드를 가리켜줌
			}
		}
		
		// 출력
		System.out.println(sb);
	}

}