- 문제 URL
- 문제 요구사항
- 접근 방법
- 풀이 순서
- 소스코드
- 문제 풀이 결과
문제 URL
BOJ : 5639_이진 검색 트리
문제 요구사항
- 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
- 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다.
- 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다.
- 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
- 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
- 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다.
- 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.
- 입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
접근 방법
- 노드 정보 받을 때, 개수를 입력 받지 않는다. -> EOF 처리를 해줘야 한다.
- 입력 받은 노드들을 1차원 배열에 담고, 해당 배열을 후위 탐색한다.
풀이 순서
- 노드 정보를 입력 받는다.
- 후위 탐색 진행
- start의 값이 end 이상이면 return(종료)
- start의 값이 end -1 과 같다면 tree 배열의 start 출력 후 return(종료)
- idx에 start + 1 대입
- idx 값이 end보다 작으면 계속해서 while문 반복
- tree의 start 값이 tree의 idx 값보다 작으면 반복문 종료, 아니라면 idx ++해서 계속해서 값 찾음
- 재귀로 해당 후위 탐색 함수 (start + 1, idx) 와 (idx, end) 호출
- tree의 start 인덱스 값 출력
소스코드
#include <iostream>
using namespace std;
long long tree[10000];
int tree_idx = 0;
void input() {
long long node;
while (cin >> node) {
if (cin.eof() == true) break;
tree[tree_idx] = node;
tree_idx++;
}
}
void postOrder(int start, int end) {
if (start >= end)
return;
if (start == end - 1) {
cout << tree[start] << "\n";
return;
}
int idx = start + 1;
while (idx < end) {
if (tree[start] < tree[idx]) {
break;
}
idx++;
}
postOrder(start + 1, idx);
postOrder(idx, end);
cout << tree[start] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
postOrder(0, tree_idx);
return 0;
}
문제 풀이 결과
