[백준/JAVA] 5639_이진검색트리

백준🔗

5639번: 이진 검색 트리

 

 

문제

 

간단 풀이

Scanner 로 입력을 받으면서 sc.hasNext()를 사용했는데 EOF(End of File)가 입력되지 않아서 무한 대기의 상태에 빠졌다. (그것도 모르구 while문이 무한 루프를 돌고 있는 건가 여기 저기 테스트 해보느라 좀 헤맸다...)

테케 입력에서 EOF가 주어지지 않을 때 로컬에서 테스트 해보고 싶다면 Ctrl + Z를 이용해서 입력을 끝내주도록 하자!!

백준에서는 그대로 제출해도 잘 채점된다.

※ EOF는 운영체제에 따라 다른데 유닉스는 Ctrl + D, 윈도우는 Ctrl + Z라고 한다.

 

처음 접근은 입력을 받으면서 1차원 배열로 트리를 구현하여 후위 순회 결과를 출력하고자 했다.

스택을 사용해서 이전 결과들을 보관하며 입력값이 이전 값보다 큰 경우와 작은 경우를 나눠서 오른쪽 자식과 왼쪽 자식으로 구별해서 트리를 만들었다.

주어진 테케에서는 답이 잘 나오길래 제출했지만 ArrayIndexOutOfBounds 에러가 발생했다...

생각해보니 트리가 한쪽으로 치우쳐서 생길 경우 노드가 10000개 있으면 2^10000-1 만큼의 배열 크기가 필요하니 이 방식은 불가능임을 깨달아 버렸다.. 🤯🤯

자료 구조 배열 말고 다른 것으로 바꿔서 할 수 없을까 좀 미련을 갖다가..

 

처음 코드

import java.util.Scanner;
import java.util.Stack;

public class Main {
	static int[] tree;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<Pair> st = new Stack<>();
		tree = new int[10001]; // 노드 개수 최대 10000개

		// 루트 노드 먼저 입력받아서 스택&트리에 넣기
		int key = sc.nextInt();
		st.add(new Pair(key, 1));
		tree[1] = key;
		int num = 1;
		// 입력이 있으면 계속 입력 받기 (전위 순회)
		while (sc.hasNext()) {
			key = sc.nextInt();
			if (key < st.peek().key) { // 이전 입력받은 수보다 작으면 왼쪽 자식
				Pair top = st.peek();
				st.add(new Pair(key, top.idx * 2));
				tree[top.idx * 2] = key;
			} else { // 이전 입력받은 수보다 크면
				// 스택이 비거나 or 스택 가장 위에 나보다 큰 수가 올 때까지 꺼내기
				Pair tmp = st.pop();
				while (!st.isEmpty() && key > st.peek().key) {
					tmp = st.pop();
				}
				// tmp의 오른쪽 자식으로 추가하기
				st.add(new Pair(key, tmp.idx * 2 + 1));
				tree[tmp.idx * 2 + 1] = key;
			}
		}

		// 트리 완성! 이제 후위 순회해서 출력
		postTraverse(1);
		System.out.println(sb);
	}

	private static class Pair {
		int key, idx;

		public Pair(int key, int idx) {
			this.key = key;
			this.idx = idx;
		}

		@Override
		public String toString() {
			return "Pair [key=" + key + ", idx=" + idx + "]";
		}
	}

	private static void postTraverse(int x) {
		// 기저 조건
		if (tree[x] == 0) {
			return;
		}

		// 유도 조건
		// L
		postTraverse(x * 2);
		// R
		postTraverse(x * 2 + 1);
		// V (출력)
		sb.append(tree[x] + "\n");
	}
}

 

다른 풀이법을 참고해서 해결했다..!!ㅎㅎ

이진 검색(탐색) 트리의 특징을 이용해서 키가 작은 것은 왼쪽 서브트리, 키가 큰 것은 오른쪽 서브 트리로 나누어서 후위 순회를 하는 방법이다.

자세한 내용은 코드 참고..🙃

 

 

코드

import java.util.Scanner;

public class Main {
	static int[] tree;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		tree = new int[10000];

		int i = 0;
		// 입력이 있으면 계속 입력 받기 (VLR)
		while (sc.hasNext()) {
			tree[i++] = sc.nextInt();
		}

		// 현재 i는 트리에 있는 노드 개수
		postTraverse(0, i);
		System.out.println(sb);
	}

	private static void postTraverse(int start, int end) {
		// 기저 조건
		if (start >= end) {
			return;
		}

		// 유도 조건
		// L과 R의 구분 지점 찾기
		int i = 0;
		for (i = start + 1; i < end; i++) {
			if (tree[i] > tree[start]) {
				break;
			}
		}
		// L
		postTraverse(start + 1, i);
		// R
		postTraverse(i, end);
		// V (출력)
		sb.append(tree[start] + "\n");
	}
}

 

 

참고 자료

(Java/자바) - 백준(BOJ) 5639번 : 이진 검색 트리