[Algorithm] Baekjoon 4256번 : 트리

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

4256번: 트리

int t, n;
 
int preOrders[1001] = { 0 };
int inOrders[1001] = { 0 };
int inOrdersIndices[1001] = { 0 };
 
 
void getPostOrders(int preOrdersStart, int preOrdersEnd, int inOrdersStart, int inOrdersEnd)
{
    if (preOrdersStart > preOrdersEnd || inOrdersStart > inOrdersEnd) return;
 
    int rootNum = preOrders[preOrdersStart];
    int rootNumIndexInInOrders = inOrdersIndices[rootNum];
    int leftSubtreeSize = rootNumIndexInInOrders - inOrdersStart; // rootNode의 좌측트리 노드 갯수
    
    getPostOrders(preOrdersStart+1,preOrdersStart+leftSubtreeSize,inOrdersStart, rootNumIndexInInOrders -1); // 좌측
    getPostOrders(preOrdersStart+leftSubtreeSize+1,preOrdersEnd, rootNumIndexInInOrders+1,inOrdersEnd); // 우측
 
    printf("%d ", rootNum);
}
 
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> t;
 
    for (int i = 0; i < t; ++i)
    {
        cin >> n;
 
        memset(preOrders, 0, sizeof(preOrders));
        memset(inOrders, 0, sizeof(inOrders));
        memset(inOrdersIndices, 0, sizeof(inOrdersIndices));
 
        for (int j = 0; j < n; ++j)
        {
            cin >> preOrders[j];
        }
 
        for (int j = 0; j < n; ++j)
        {
            cin >> inOrders[j];
            inOrdersIndices[inOrders[j]] = j;
        }
 
        getPostOrders(0, n - 1, 0, n - 1);
        printf("\n");
    }
    
    return 0;
}

 

저번에 풀었던 트리문제에서 순서만 바뀐 문제다.

저번 문제는 중위,후위 순회를 주고 전위순회를 구하라는 문제였는데, 이번엔 전위,중회를 주고 후위순회를 구하는 문제였다.

그때 좀 인덱스계산하는게 헷갈려서 한번에 풀진 못했는데 이번엔 그래도 스스로 잘 풀었다.

여담으로 맞게 작성했는데도 8%에서 실패가 떠서 다른사람 풀이를 봤더니 내꺼랑 동일했다.

그래서 뭐가문젠가 생각하다가 혹시나 해서 51번째줄의 cout <<endl을 printf("\n") 으로 바꿨더니 그제서야 통과가 됐었다...