링크
https://www.acmicpc.net/problem/5639
문제 설명
정답률 38.056%
이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
입력 예제
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 개 이하이다. 같은 키를 가지는 노드는 없다.
50
30
24
5
28
45
98
52
60출력 예제
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
5
28
24
45
30
60
52
98
50풀이
전위 순회 결과가 입력값으로 주어지고 이를 후위 순회하여 다시 출력해야 한다.
우선 전위 순회한 결과를 배열로 저장한다. 배열의 크기는 노드의 수의 최댓값인 10,000으로 한다.
int[] preorder = new int[10_000];
int index = 0;
String input;
while ((input = br.readLine()) != null) {
preorder[index++] = Integer.parseInt(input);
}후위 순회는 왼쪽 -> 오른쪽 -> 루트 순으로 탐색하여야 하므로, 이진 탐색을 진행하며 오른쪽 서브트리의 시작점을 찾는다.
int parent = preorder[start];
int mid = start + 1; //오른쪽 서브트리의 시작점
//오른쪽 서브트리 시작점 찾기
while (mid <= end && preorder[mid] < parent) {
mid++;
}우선 한 번 탐색을 진행하면 오른쪽 서브트리의 시작점인 98의 인덱스 6을 기준으로 왼쪽과 오른쪽을 구분한다. 그리고 시작점과 끝점을 갱신하여 왼쪽, 오른쪽 각각 재귀를 호출한다.
//왼쪽 서브트리 후위 순회
postorder(start + 1, mid - 1);
//오른쪽 서브트리 후위 순회
postorder(mid, end);이렇게 반복을 하면서 부모 노드를 입력값으로 저장한다.
부모/왼쪽 /오른쪽
50 / 30 24 5 28 45 / 98 52 60
//왼쪽 서브트리부터 탐색 (30 24 5 28 45)
부모/왼쪽 /오른쪽
30 / 24 5 28 / 45
//왼쪽 서브트리부터 탐색 (24 5 28)
부모/왼쪽/오른쪽
24 / 5 / 28
5 //자식 노드가 없으니 재귀 종료
28 //자식 노드가 없으니 재귀 중료
.
.
.전체 코드
//백준
public class Main {
static int[] preorder = new int[10_000];
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int index = 0;
String input;
while ((input = br.readLine()) != null) {
preorder[index++] = Integer.parseInt(input);
}
postorder(0, index - 1);
System.out.println(sb);
}
//서브트리의 범위를 지정하여 후위 순회
private static void postorder(int start, int end) {
if (start > end) {
return;
}
int parent = preorder[start];
int mid = start + 1; //오른쪽 서브트리의 시작점
//오른쪽 서브트리 시작점 찾기
while (mid <= end && preorder[mid] < parent) {
mid++;
}
//왼쪽 서브트리 후위 순회
postorder(start + 1, mid - 1);
//오른쪽 서브트리 후위 순회
postorder(mid, end);
//부모 노드를 저장
sb.append(parent).append("\n");
}
}