<백준 알고리즘> 2263번 트리의 순회(분할정복)

백준 2263번

접근 방식

주어진 inorder과 postorder를 고려해 봤을 때 postorder을 통해서 루트를 얻어올 수 있고 inorder를 통하여 미리 구한 루트를 기준으로 왼쪽 서브트리 오른쪽 서브트리를 구할 수 있다는 것을 알아냈다.

1. 이를 구현하기 위해 postorder의 가장 마지막 값은 무조건 root의 값이므로 이를 기점으로 시작하여 root의 왼쪽 subroot 오른쪽 subroot를 구하는 방식으로 접근한다.

2. subroot를 구하기 위하여 처음에 쓴 방식은 루트를 구했다면 이를 기준으로 inorder에서 해당 루트 인덱스 왼쪽은 왼쪽 서브트리 set ,오른쪽은 오른쪽 서브트리 set에 넣어 postorder을 맨뒤에서 부터 순회할 때 오른쪽 왼쪽 각각 가장 먼저 set안에 해당하는 값이면 이것이 그 subtree의 root임을 이용하였다.

3. 자료구조의 트리처럼 왼쪽, 오른쪽 포인터를 이용한 구조체를 만들어서 하였는데 시간초과도 나고 불필요하다는 생각이 들어 재귀를 통해 함수에 접근할때 바로 출력하면 그것이 preorder이기 때문에 구조체 방법을 없애고 바로바로 출력하는 방법으로 바꾸었다.

4. 여전히 시간초과가 나서 subroot를 찾을때 오른쪽 subroot는 postorder배열에서 현재 root의 바로 옆에있는 것이기에 왼쪽 subroot를 구할때 오른쪽 개수만큼 뺀후에 시작하도록 하였는데 이래도 여전히 시간초과가 발생했다.

5. 마지막으로 시도한 방법은 오른쪽은 현재 root바로 옆 인덱스의 값을 반환하도록 하고 왼쪽은 아까 시도한 방식에서 for문을 없애고 현재 인덱스에서 오른쪽 서브트리의 개수 + 1의 값을 뺴서 이 역시도 해당 인덱스에 위치한 배열 값을 출력하도록 했고 문제가 해결이 됐다.

처음 접근 방식은 좋았는데 이를 효율적으로 구현하지 못하여 좀 헤맸던 것 같다.

해당 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>


using namespace std;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int N;

int InOrder[100001] = { 0 };
int PostOrder[100001] = { 0 };

unordered_map<int,int>InOrderIdx;
unordered_map<int,int>PostOrderIdx;


int FindLeftTreeRoot(int rootIdx, int postRootIdx, int end) {
	
	int rightNums = end - rootIdx;  
	int leftRootIdx = postRootIdx - rightNums - 1;  

	if (leftRootIdx >= 1) {
		return PostOrder[leftRootIdx];
	}
	return -999;
}

int FindRightTreeRoot(int rootIdx, int postRootIdx) {
	
	int rightRootIdx = postRootIdx - 1;  

	if (rightRootIdx >= 1) {
		return PostOrder[rightRootIdx];
	}
	return -999;
}

void MakeTree(int start, int end, int rootVal, int rootIdx)
{

	if (start > end)
	{
		return;
	}

	int rootV = -999;
	int postRootIdx = PostOrderIdx[rootVal];
	
	cout << rootVal << " ";

	if ((rootV = FindLeftTreeRoot(rootIdx, postRootIdx, end)) != -999)
	{
		MakeTree(start, rootIdx - 1, rootV, InOrderIdx[rootV]);
	}

	if ((rootV = FindRightTreeRoot(rootIdx, postRootIdx)) != -999)
	{
		
		MakeTree(rootIdx + 1, end, rootV, InOrderIdx[rootV]);
	}
	
;

}



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> InOrder[i];
		InOrderIdx[InOrder[i]] = i;	
	}

	for (int i = 1; i <= N; i++)
	{
		cin >> PostOrder[i];
		PostOrderIdx[PostOrder[i]] = i;
	}

	int rootVal = PostOrder[N];

	MakeTree(1, N, rootVal,InOrderIdx[rootVal]);

	
	int a = 0;

	return 0;
}