[백준 2263] 트리의 순회

인덱스 위치를 헷갈려서, 그리고 이유 모를 시간초과 문제로 몇 차례 실패했던 문제이다.

종이에 쓰면서, 이해를 하려고 노력하니 이해가 되었지만....

아직 100퍼센트 이해가 되지 않은 것 같아, 노력이 필요하다

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

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

예제 입력 1

3
1 2 3
1 3 2

예제 출력 1

2 1

천천히 생각해보다 보아하니, PostOrder의 맨 뒤가 root인것을 활용하고, 그 root를 가지고 있는 InOrder와 InOrder_Start(is)의 거리를 생각하면 어디가 left이고 right인지 구분할 수 있다.

이때, InOrder의 요소를 인덱스로 갖는 position 배열의 값은 InOrder 요소의 index를 값으로 가진다. (천천히 이해하자!!)

소스코드

#include<iostream>
 
using namespace std;
 
int n, postOrder[100000], inOrder[100000], position[100000];
 
void solve(int is, int ie, int ps, int pe){
    if(is > ie || ps > pe)    
        return;
    int root = postOrder[pe];
    cout << root << ' ';
    int p = position[root];
    int left = p - is;
    cout << root << ' ' << p << ' ' << left << '\n';
    
    solve(is,p-1,ps,ps+left-1);
    solve(p+1,ie,ps+left,pe-1);
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> inOrder[i];
    for(int i = 0; i < n; i++)
        cin >> postOrder[i];
    for(int i = 0; i < n; i++)
        position[inOrder[i]] = i;
    for(int i = 0; i < n+1; i++)
        cout << position[i] << ' ';
    cout << '\n';
        
    solve(0,n-1,0,n-1);
}
 

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.