[Gold V] 이진 검색 트리 - 5639
성능 요약
메모리: 16088 KB, 시간: 376 ms
분류
그래프 이론, 그래프 탐색, 재귀, 트리
제출 일자
2024년 1월 10일 21:12:46
문제 설명
이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
입력
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.
출력
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
접근 방식
1. 전위순회(VLR)로 입력 받은 그래프의 원본을 만든다.
2. 그래프를 통해서 후위순위한 결과를 반환한다.
그래프의 원본을 만드는 과정
값을 입력 받았을 때 루트보다 작다면 왼쪽, 크다면 오른쪽 서브트리인 이진트리이다.
1. 루트로부터 값을 입력 받은 뒤 현재 값보다 크다면,오른쪽 작다면 왼쪽으로 보낸다.
2. 다음 연결 노드가 Null이라면 연결해준다.
// 노드 값 입력 받음
int node = Integer.parseInt(tmp);
// 루트부터 시작하여 현재 입력 값을 넣을 위치를 찾는다.
// 즉 그래프를 먼저 만들어준다.
Node pos = root;
while (true) {
// 값이 현재 값보다 작다면 왼쪽
if (pos.value > node) {
// 만약 왼쪽 노드가 존재하지 않는다면 그 자리에 입력 값을 노드로 위치시킨다.
if (pos.left == null) {
pos.left = new Node(node);
break;
}
// 존재한다면 pos를 pos.left로 갱신한다.
else {
pos = pos.left;
}
}
// 현재 값보다 크다면 오른쪽
else {
// 오른쪽 노드가 존재하지 않는다면 그 자리에 입력 값을 노드로 위치 시킨다.
if (pos.right == null) {
pos.right = new Node(node);
break;
}
// 존재한다면 pos를 pos.left로 갱신한다.
else {
pos = pos.right;
}
}
}
}
후위순위(LRV)로 결과를 만드는 과정
1. 루트부터 시작하여 확인한다.
2. 왼쪽 노드를 확인 후 연결되어 있다면 재귀 호출(Left Node)
3. 오른쪽 노드 확인 후 연결되어 있다면 재귀 호출(Right Node)
4. 현재 노드의 값을 StringBuilder에 넣어준다.(V Node)
// 후위순위로 출력
private static void LRV(Node node) {
// 왼쪽 노드가 null이 아니라면(연결되어 있다면) 재귀 호출
if (node.left != null) {
LRV(node.left);
}
// 오른쪽 노드가 null이 아니라면(연결되어 있다면) 재귀 호출
if (node.right != null) {
LRV(node.right);
}
// 시간을 단축시키기 위해 현재 노드의 값을 출력하는 것이 아닌 StringBuilder에 넣어준다.
sb.append(node.value).append("\n");
}
전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
class Main {
// 그래프를 만들기 위한 노드 클래스
static class Node {
int value;
Node left, right;
Node(int value) {
this.value = value;
}
}
// 출력하는 시간을 줄이기 위한 StrignBuilder
static StringBuilder sb = new StringBuilder();
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 처음 입력 받은 값은 무조건 루트 노드이다. -> 전위순회이기때문에
Node root = new Node(Integer.parseInt(br.readLine()));
String tmp;
while (true) {
// 입력 받은 값이 null이거나 비어있다면 EOF이므로 종료
tmp = br.readLine();
if (tmp == null || tmp.isEmpty()) {
break;
}
// 노드 값 입력 받음
int node = Integer.parseInt(tmp);
// 루트부터 시작하여 현재 입력 값을 넣을 위치를 찾는다.
// 즉 그래프를 먼저 만들어준다.
Node pos = root;
while (true) {
// 값이 현재 값보다 작다면 왼쪽
if (pos.value > node) {
// 만약 왼쪽 노드가 존재하지 않는다면 그 자리에 입력 값을 노드로 위치시킨다.
if (pos.left == null) {
pos.left = new Node(node);
break;
}
// 존재한다면 pos를 pos.left로 갱신한다.
else {
pos = pos.left;
}
}
// 현재 값보다 크다면 오른쪽
else {
// 오른쪽 노드가 존재하지 않는다면 그 자리에 입력 값을 노드로 위치 시킨다.
if (pos.right == null) {
pos.right = new Node(node);
break;
}
// 존재한다면 pos를 pos.left로 갱신한다.
else {
pos = pos.right;
}
}
}
}
// 루트노드부터 시작
LRV(root);
System.out.println(sb);
}
// 후위순위로 출력
private static void LRV(Node node) {
// 왼쪽 노드가 null이 아니라면(연결되어 있다면) 재귀 호출
if (node.left != null) {
LRV(node.left);
}
// 오른쪽 노드가 null이 아니라면(연결되어 있다면) 재귀 호출
if (node.right != null) {
LRV(node.right);
}
// 시간을 단축시키기 위해 현재 노드의 값을 출력하는 것이 아닌 StringBuilder에 넣어준다.
sb.append(node.value).append("\n");
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 14500번 : 테트로미노 Gold4(골드4) - JAVA[자바] (0) | 2024.01.12 |
---|---|
[백준] 1753번 : 최단경로 Gold4(골드4) - JAVA[자바] (0) | 2024.01.11 |
[백준] 3190번 : 뱀 Gold4(골드4) - JAVA[자바] (2) | 2024.01.08 |
[백준] 12100번 : 2048(Easy) Gold2(골드2) - JAVA[자바] (1) | 2024.01.06 |
[백준] 2636번 : 치즈 Gold4(골드4) - JAVA[자바] (1) | 2023.12.26 |