알고스팟 (algospot) TRAVERSAL - 트리 순회 순서변경

종만북 문제를 풀었다.

난이도 하인데 개인적으로 어려웠다.

실수 한 점 1. 처음 든 생각으로는 전위 순회로만 트리를 구성할수 있지 않나? 였다. 실제로 그려보니 전위순회로 가능할 것 같았다. 그래서 그렇게 문제를 풀었다. 하지만 예제조차 나오지 않았다. ㅠㅠ 난이도 하라며..

현재 노드와 추가될 노드의 크기를 비교하여 작으면 왼쪽에 추가해주었다. 클경우에는 오른쪽에 추가해줘야하는데, 부모보다 클경우에는 부모노드보다 작을때까지 위로 올라가도록 구현하였다.

이렇게 구현하니, 루트 노드의 오른쪽에 진입한 순간 오른쪽 자식은 항상 부모노드보다 크게 된다. 이런 예외가 생기니 어떻게 하지? 하다가 포기하고 종만북을 본 것 같다.

실수한 점 2. 트리를 만들려고 했던 것이 문제였다. 충분히 비슷한 문제를 많이 풀어봤음에도 탐색하며 순서바꿔 출력할 생각은 안하고 트리를 만들 생각을했다. 그러니 문제가 더 복잡하고 힘들게 느껴졌다.

배운점:

종만북을 보고도 사실 잘 이해가 가지 않았다. 사실 이해가 가지 않았다기 보단 내게 익숙하지 않은 STL을 사용하고 있어 이해하기 싫었다는게 더 맞는 표현인 것 같다. 나는 이럴때 무작정 손으로 쓴다. 손으로 한줄 쓰고 이해하고 한줄쓰고 이해하고.. 그냥 읽는것보다 최종적으로 더 이해가 간 느낌이다. 

무튼 find함수라던지 find함수에서 원소를 찾고 그 인덱스를 구하기위해 이터레이터 값을 다시 빼주는 기법이라던지 배울게 많았던 문제였다. 또한 전위순회와 중위순회에서 연관성을 찾은것도 생각하지 못했다. 전위순회의 첫 탐색부분이 그 서브트리의 루트 노드이고, 중위순회에서 그 루트 값을 기준으로 왼쪽은 왼쪽자식 오른쪽은 오른쪽자식이다..전위순회에서는 루트노드가 먼저나오고 그다음 루트를 기준으로 왼쪽자식, 그다음 오른쪽 자식이 나온다.

전위순회에서 서브트리마다의 루트를 찾고 중위순회에서 왼쪽자식의 갯수를 구하고 이를 이용해 왼쪽과 오른쪽자식을 잘라 탐색을하여 모든 트리를 탐색하는법을 사용했다.

멋졌다.

나중에 한번 더 풀어봐야겠다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> slice(const vector<int>& v, int a, int b){
    return vector<int>(v.begin() + a, v.begin() + b);
}
 
 
void printPostOrder(const vector<int>& preorder, const vector<int>& inorder){
    const int N = preorder.size();
    if(preorder.empty()) return;
 
    const int root = preorder[0];
    const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
 
    printPostOrder(slice(preorder,1,L + 1),slice(inorder,0,L));
    printPostOrder(slice(preorder,L+1, N), slice(inorder,L+1, N));
    printf("%d ", root);
}
 
 
int main() {
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        vector<int> preorder, inorder;
        for(int i = 0 ; i < n; i++){
            int t;
            scanf("%d", &t);
            preorder.push_back(t);
        }
        for(int i = 0 ; i < n; i++){
            int t;
            scanf("%d", &t);
            inorder.push_back(t);
        }
        printPostOrder(preorder, inorder);
    }
    return 0;
}