백준 5639, 이진 검색 트리 - Tree (Binary Search Tree), Recursive

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



좋은 웹페이지 즐겨찾기