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

in-order traversal, post-order traversal이 주어졌을 때 pre-order traversal을 구하는 문제입니다.

solve(int in_st, int post_st, int len) 함수를 in[in_st:in_st+len], post[post_st:post_st+len]를 보고 pre order를 출력하는 함수라고 생각해봅시다.

주어진 예시

3

1 2 3

1 3 2

에서 solve(0, 0, 3)은 2 1 3을 출력하는 함수입니다.

이 solve() 함수에서 divide and conquer 아이디어가 들어가는건데, 바로 root를 기준으로 solve 함수를 더 작은 2개로 쪼갤 수 있습니다.

solve(0, 0, 3)은

print 2

solve(0, 0, 1)

solve(1, 2, 1) 로 분할이 가능합니다.

즉, post[post_st+len-1]에 적힌 값이 root이고 그 root가 in-order 상에서 어디 있는지만 알아내면 solve를 분할할 수 있습니다. 번호는 1부터 n번까지 매겨지기 때문에 그냥 각 번호가 in-order 상에서 어디에 위치하는지 알아내는 배열을 미리 만들어두면 최종적으로 O(N)에 문제를 해결할 수 있게 됩니다. 코드는 좀 더럽게 짰네요.

https://github.com/encrypted-def/BOJ/blob/master/2263.cpp