https://www.acmicpc.net/problem/5639
5639번: 이진 검색 트리
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다
www.acmicpc.net
이 문제의 경우 이진 검색 트리이긴 하지만 나는 굳이 따지자면 분할 정복이라고 봐도 될거 같다. 그 이유는 이문제의 경우
pivot을 기준으로 계속 나눠가면서 트리를 분리해서 출력을 해주어야 한다. 기존에 이진트리가 자신의 인덱스/2가 부모로 배열을 사용하는 것과 달리 특이하게 들어 왔다. 일단 이문제의 풀이는 아래 사진처럼 배열을 나누어야 했다.
#include <iostream>
using namespace std;
int arr[10005];
void post(int start, int end) {
if (start >= end) return;
//else if (start == end-1) {
// cout << arr[start] << endl;
// return;
//}
int i;
for (i = start + 1; i < end; i++)
if (arr[start] < arr[i])
break;
post(start + 1, i);
post(i , end);
cout << arr[start] << endl;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int num;
int idx=0;
//while (true) {
// cin >> num;
// if (num == 0) {
// break;
// }
// else {
// arr[idx] = num;
// idx++;
// }
//}
while (cin >> num) {
arr[idx] = num;
idx++;
}
post(0, idx);
}일단 이 문제는 입력 방식을
while (cin >> num) {
arr[idx] = num;
idx++;
}이렇게 작성해 주어야 했는데 그이유는 이문제는 EOF를 통해 입력의 끝을 알기 때문에 우리가 프롬프트창에서 직접 사용자 입력을 해주게 되면 cin 의 기능이 끝나지 않는다 이에 나는 테스트 할때 main함수 부분의 주석을 해제해서 사용했다.
또한 이 문제의 경우 나의 post함수에 주석 부분은 성능을 올리기 위함이지만 가독성으로 볼때는 주석처리를 하는게 맞다.
그 이유는 위에 첨부한 풀이 그림을 보았을 때 원소가 2개남았을 때 무조건 start가 leaf단계이기 때문에 더이상 분할 할 필요가 없기 때문이다 하지만 맨끝에 원소가 하나 남았을 때는 굳이 출력을 해줄 필요가 없다. 이에 나는 원소가 하나 남았다는 것
if (start >= end) return;을 이런식으로 start 인덱스와 end 인덱스가 같을 때 함수를 return 하여 더 이상 진행되지 않도록 하였다