트리 - 트리 순회 순서 변경

 

트리 - 트리 순회 순서 변경

 

 

문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/TRAVERSAL

 

 

 

 

 

트리

계층적 구조를 갖는 자료들을 표현하기 위한 자료구조

ex) 대진표, 조직도, 상품 분류 등등

 

 

 

 

풀이 생각 (삽질)

1. 어떻게 전위랑 중위를 가지고 후위를 찾을까?

 1) 전위와 중위를 보고 전체 트리를 만든 후, 후위 탐색을 할까? (트리를 만든 후 후위 탐색)

 2) 전위와 중위를 살펴보면서 후위 탐색 (하나씩 살펴보면서 후위 탐색 출력)

 

2. 왼쪽 오른쪽 어떻게 구분할까?

 - preorder의 첫번째가 root이고, inorder에서 root가 나오기 전까지 왼쪽인 것을 발견.

 - inorder에서 왼쪽을 따로 넘겨주고, 오른쪽을 따로 넘겨주고, 계속 반복... 

  => 작은 조각들의 반복이다. 재귀를 사용해야겠다.

 

3. 어떻게 왼쪽 오른쪽 나눠서 넘겨줄까?

 - left vector, right vector 만들어서 넘겨주기

  => vector 4개로 하니 복잡해짐. slice vector로 2개만.

 - 그렇다면 slice vector에는 무엇을 담아줘야할까?

 =>

 slice_inorder 에는 왼쪽or오른쪽 vector의 크기만큼 -> 크기를 구해주자

 slice_preorder에는 현재 root의 왼쪽or오른쪽 vector의 크기만큼 -> 크기를 구해주자

 구한 크기만큼 잘라서 재귀 돌리기

 

4. 자르는 방법은..?

 왼쪽or오른쪽 크기만큼 잘라야한다. 

 - 필요한 것 = left, right의 크기, slice_in, slice_preorder

 

=> 자르는 방법에서 시간을 많이 써서 그냥 답 코드를 봤음. 답 코드는 아래.

 

 

answer code

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
 
vector<int> slice(const vector<int>& v, int a, int b) {
    return vector<int>(v.begin() + a, v.begin() + b);
}
 
void func(const vector<int>& pre, const vector<int>& in) {
    if (pre.empty()) return;
 
    int root = pre[0];
    const int left_size = find(in.begin(), in.end(), root) - in.begin();
    const int right_size = pre.size() - left_size - 1;
 
    func(slice(pre, 1, left_size+1), slice(in, 0, left_size));
    func(slice(pre, left_size+1, pre.size()), slice(in, left_size+1, pre.size()));
 
    cout << root << ' ';
}
 
int main() {
    cin.sync_with_stdio(false);
 
    int T;
    vector<int> preorder;
    vector<int> inorder;
 
    cin >> T;
 
    while (T--) {
        cin >> n;
        preorder.assign(n, 0);
        inorder.assign(n, 0);
        for (int i = 0; i < n; ++i) {
            cin >> preorder[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> inorder[i];
        }
        func(preorder, inorder);
    }
    return 0;
}

 

 

 

 

Feedback

1. 나는 slice_in 과 slice_pre 라는 vector를 만들어 for문으로 push_back을 하며 대입했음. 구종만은 vector<int>를 리턴값으로 하여 slice 함수를 만들어버림.

 => 물론 push_back하면 되긴했지만, 시작과 끝을 받아 vector로 리턴하는게 보기도 깔끔하고 목적에 맞는 것 같음.

 

2. 바꾸지 않는 매개변수에 const 붙히기

 

3. 트리는 재귀다.

 => 100퍼센트라곤 할 순 없지만, 일단 트리가 나오면 재귀부터 생각해봐야할 듯.

 => 작은 조각들의 반복. 계층적 구조.

 

 

● 생각하는 것까진 느낌이 좋았으나 구현에서 시간을 많이 잡아먹었다.

 => 구현부분이 많이 부족함을 느낌