4256

전위탐색에서의 값을 중위탐색에서 찾으면 그것의 왼쪽에 있는 것들은 left child, 오른쪽에 있는 것들은 right child이다. 이 성질을 이용해서 풀면 쉽게 풀수있다.

재귀함수를 이용해 좀 더 깔끔히 푸는 방식이 있으나 나는 규칙성과 stack을 같이 응용해 풀었다.

#include<iostream> #include<cstdio> #include<stack> using namespace std; int d[1005]; int pre[1005]; int ior[1005]; int main() { int tc, size; stack<int> s; scanf("%d", &tc); d[0]=1; while(tc--) { scanf("%d", &size); d[size+1]=1; for(int i=1; i<=size; i++) { d[i]=0; scanf("%d", &pre[i]); } for(int i=1; i<=size; i++) { scanf("%d", &ior[i]); } int piv=1; int prob; while(piv<=size) { for(prob=1; ior[prob]!=pre[piv]; prob++){} d[prob]=1; s.push(prob); while(!s.empty() && d[s.top()-1]==1 && d[s.top()+1]==1) { printf("%d ", ior[s.top()]); s.pop(); } piv++; } printf("\n"); } return 0; }