[백준 5639] 알고리즘 125일차 : 이진 검색 트리

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

C++ 트리

트리를 전위순회한 결과를 입력받아 동일한 트리를 후위순회한 결과를 출력하는 문제

 

접근방법

1. 원래의 트리를 재현하여 후위순회를 구하는 방법
2. 전위순회에서 바로 후위순회를 구하는 방법
중에 2번을 선택했다.

전위순회한 결과가 50 30 24 5 28 45 98 52 60 이거라면
여기서 50 | 30 24 5 28 45 | 98 52 60 이렇게 부모노드 | 왼쪽 서브트리 | 오른쪽 서브트리로 나눌 수 있다.

prorder_traverse함수가 배열의 시작 위치와 끝 위치를 인수로 전달받으면
배열을 분할할 경계, 즉 왼쪽 서브트리와 오른쪽 서브트리의 경계를 구해야한다.
이는 배열의 값을 왼쪽부터 봤을때 부모노드의 값보다 값이 큰 첫번째 수를 찾으면 되는데
선형탐색으로 찾으면 시간이 오래걸리기 때문에 이분탐색을 사용하여 찾는다.

위와 같이 배열을 분할한 후,
후위순회 결과를 출력하는 것이기 때문에 아래와 같은 순서로 함수를 호출한다.

왼쪽 서브트리에 대해 prorder_traverse 함수를 호출하고,
오른쪽 서브트리에 대해 prorder_traverse 함수를 호출하고,
마지막으로 부모노드를 출력한다.

그리고 이 문제는 입력의 개수가 정해져 있지 않다.
그래서 while문으로 아무것도 입력되지 않을 때 까지 입력되는 식의 처리를 해야한다.

사용한 알고리즘 : 트리, 재귀, 분할정복, 이분탐색
사용한 자료구조 : 배열(벡터)

오답노트

휴 이분탐색이랑 경계 범위 초과 고려할 때 경계 값을 정하는데에 아직 많이 익숙하지 않은 것 같다.
한번에 잘 풀리는 날도 있는데 오늘은 집중이 너무 안돼서 오래걸렸다.
그리고 C++에서 최근에 vector의 사이즈가 unsigned long이어서 int인 값이랑 비교하거나 연산을 하려고 하면 워닝을 띄운다.
매번 타입캐스팅하는 것도 귀찮아서 그냥 넘기는데 역시 최적화를 위해선 고쳐줘야겠지..
요즘 라이브러리 안쓰는 것에 약간 익숙해져서 배열을 써볼까 했는데 input 개수가 정해져있지 않아서 카운팅해야 하는데 변수 여러개 쓰는것도 보기싫어서 그냥 vector썼다. (주절주절)

소스코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;

int binarySearch(int target, int s, int e){
    int mid = (s+e)/2;
    while(s <= e){
        mid = (s+e)/2;
        if(v[mid] > target){
            e = mid-1;
        }else{
            s = mid+1;
        }
    }
    return s;
}

void prorder_traverse(int s, int e){
    if(s == e){
        cout << v[s] << "\n";
    }else if(s < e){
        int ns = binarySearch(v[s], s+1, e);
        prorder_traverse(s+1, ns-1);
        prorder_traverse(ns, e);
        cout << v[s] << "\n";
    }
}

int main(){
    int n;
    while(cin >> n)
        v.push_back(n);

    prorder_traverse(0, v.size()-1);
    
    return 0;
}