📘 문제

문제링크 : https://www.acmicpc.net/problem/2263 (단계별로 풀어보기 : 트리)

📝 문제 풀이

맨 처음 문제를 접했을 때 문제 풀이법이 바로 생각이 나지 않았다. 두번째 다시 볼때 30분동안 차근히 inorder와 postorder에서 나오는 특징을 생각해봤다!

❗️inorder의 특징 : 가장 왼쪽에서 가장 오른쪽으로 진행된다.
                                   -> 즉 root 값을 알면 root기준으로 왼쪽 자식들과 오른쪽 자식들을 나눌 수 있다.
❗️postorder의 특징 : root를 기준으로 왼쪽 아래에서부터 위까지, 오른쪽 아래에서부터 위까지 그 후 마지막이 root.
                                   -> 즉 postorder를 보면 root 값을 찾을 수 있다.

이러한 특징으로 맨 처음 root값을 찾고 root의 왼쪽 자식과 오른쪽 자식 더미를 한 트리로 보고 각각의 root값을 찾는 형식으로 재귀와 분할 정복을 사용하였다. 이 때 postorder의 특징을 이용하여 root 값을 찾고, inorder의 특징을 이용하여 root값 기준으로 왼쪽은 왼쪽 자식들, 오른쪽은 오른쪽 자식들이란 것을 알 수 있다.
알고리즘은 이렇게 되겠다.
신경쓴 부분은 다음 아래다.
1. 재귀의 탈출은 자식이 없는 경우를 인덱스로 풀어주었다.
2. root를 찾고 그 위치를 inorder에서 찾을 때 반복문으로 찾게되면 함수를 호출할때마다 반복문이 돌기 때문에 처음 inorder안의 숫자들의 위치를 저장하는 별도의 벡터를 만들어서 사용했다. (시간을 줄여줍니다.)

✏️ 알고리즘 스케치

💻 소스코드

#include <iostream>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


void inputOrder(vector<int>& order, int n);
void memoRootPosition(vector<int>& rootPosition, vector<int>& inorder, int n);
void findRoot(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd, vector<int>& rootPosition);

int main()
{
    fastio;

    int n;
    cin >> n;

    vector<int> inorder;
    vector<int> postorder;
    vector<int> rootPosition;
    inorder.resize(n);
    postorder.resize(n);
    rootPosition.resize(n+1);

    inputOrder(inorder, n);
    inputOrder(postorder, n);
    memoRootPosition(rootPosition, inorder, n);
    
    findRoot(inorder, 0, n-1, postorder, 0, n-1, rootPosition);

    return 0;
}

void inputOrder(vector<int>& order, int n)
{
    for(int i=0; i<n; i++)
        cin >> order[i];
}

void memoRootPosition(vector<int>& rootPosition, vector<int>& inorder, int n)
{
    for(int i=0; i<n; i++)
        rootPosition[inorder[i]] = i;
}

void findRoot(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd, vector<int>& rootPosition)
{
    if(inEnd<inStart) return;

    cout << postorder[postEnd] << " ";
    
    
    int leftInStart = inStart, 
        leftInEnd = rootPosition[postorder[postEnd]] - 1, 
        rightInStart = rootPosition[postorder[postEnd]] + 1, 
        rightInEnd = inEnd;

    findRoot(inorder, leftInStart, leftInEnd, postorder, postStart, postStart + leftInEnd - leftInStart, rootPosition);  // root 기준 왼쪽
    findRoot(inorder, rightInStart, rightInEnd, postorder, postStart + leftInEnd - leftInStart + 1, postEnd - 1, rootPosition);   // root 기준 오른쪽
}