[BOJ] #5639 이진 검색 트리

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

5639번: 이진 검색 트리

---

문제 요구조건은 꽤 간단하다. 전위순회로 주어진 트리를 후위순회로 변환하면 끝이다. 이때 중요한 키 포인트는 세가지가 있다. 

1. 전위순회에서 가장 첫번째 노드는 루트 노드이다.
2. 전위순회에서 루트노드보다 커지는 첫번째 원소를 기점으로 왼쪽, 오른쪽 자식트리가 나뉘게 된다.
3. 나뉜 자식트리에 대하여 1~2의 과정을 재귀 형태로 반복하고, 그 과정에서 맨 첫번째 노드(루트 노드)들을 출력해주면 자연스럽게 후위순회로 변환된다.

 

이게 말로 하면 좀 이해가 어려울수가 있는데, 그림을 직접 그려보면 이해가 훨 수월하다.

좀 별로긴 하다.

같은 색으로 표시 된 부분이 루트와 자식트리의 분기점이다. 결과적으로 재귀의 형태를 통해 자식트리들에 대해 같은 동작은 반복하게 되면, 결국 왼쪽 트리의 맨 왼쪽 자식노드가 출력값의 맨 앞에 위치하게 되고, 원래 맨 첫번째 원소였던 루트노드는 맨 뒤에 위치하게 된다.

이렇게 글로 쓰고나니 더 이해가 안되는 느낌인데, 추후에 한번 더 풀어봐야겠다. 커밋 메세지에 애스터리스크 달아 놨으니 참고.

아 그리고, 한가지 더 신경쓸것은 문제에서 주어지는 입력에 대해 명확한 입력종료 조건을 제시하지 않았다. 따라서, 입력 받을때에 while 조건에 cin 입력함수를 넣어 EOF 입력받도록 작성하였고, 그 때문인지는 모르겠지만 시간초과가 두번씩 났었다. 분명 같은 알고리즘을 풀었는데 조금씩 코드를 고치고 고치니까 또 맞혔습니다가 떴다. 뭐지...

#include <iostream>

using namespace std;

int arr[10001];

void F(int start, int end) {
    if (start >= end) return;

    int root = arr[start];
    int idx = start+1;

    while(idx < end){
        if(root < arr[idx]) break;
        idx++;
    }

    F(start+1, idx);
    F(idx, end);

    cout << arr[start] << '\n';
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int a;
    int n=0;

    while(cin >> a) arr[n++] = a;

    F(0, n);

    return 0;
}