2263 트리의 순회

2263 트리의 순회 (c++)

문제

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

접근 방식

Tree, Traversal

1. 인 오더, 포스트 오더가 주어진다.
2. 인 오더는 (왼쪽자식)나(오른쪽자식)
3. 포스트 오더는 (왼쪽자식)나(오른쪽자식)
4. 즉 포스트 오더의 맨 뒤는 항상 루트이다.
5. 이를 다시 인 오더에서 찾으면 왼쪽과 오른쪽 자식을 분류할 수 있다.
6. 이것을 다시 재귀로 호출한다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;
int In[100'000];
int Post[100'000];
int Idx[100'000];
void BT(int InStart, int InEnd, int PostStart, int PostEnd)
{
    if (InStart >= InEnd || PostStart >= PostEnd) return;
    int root = Post[PostEnd - 1];
    cout << root << ' ';
    int mid = Idx[root-1];
    BT(InStart, mid, PostStart, PostStart + mid - InStart);
    BT(mid + 1, InEnd, PostStart + mid - InStart, PostEnd - 1);
}
int main()
{
    int N;
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> In[i];
    for (int i = 0; i < N; ++i) cin >> Post[i];
    for (int i = 0; i < N; ++i) Idx[In[i]-1] = i;
    BT(0, N, 0, N);
    return 0;
}

다시 생각해 볼 점

1. 처음엔 위와 같이 탐색하여 parent, left, right 변수를 가지는 구조체 Node를 vector로 저장하여 트리를 완성했다. 그리고 그 트리를 다시 프리 오더로 탐색했다. (성공은 했는데 시간이 1.2초인가 나옴)
2. 시간이 짧게 걸린 사람들의 풀이를 보니, 굳이 트리를 완성시킬 필요 없이 root를 출력하고 왼쪽 자식 오른쪽 자식 순으로 탐색하면 됐다. (즉, 이미 재귀함수 자체가 Pre Order 형식을 띄고 있었다.)
3. 시간이 단축되어 28ms가 되었다.
4. 메모리가 7.4MB정도가 나와서 메모리 효율을 올리는 방법을 찾아보니, 다수의 사람들이 1번 코드인

    #pragma GCC optimize("Ofast")
   

   을 사용하고 있었다.

5. 나도 적용해보니 4MB 정도로 메모리 효율이 올랐다.