[백준알고리즘] 4256번: 트리-C++

4256번: 트리 (acmicpc.net)

4256번: 트리

 

이전에 풀었던 '트리의 순회' 문제와 유사하다.

[백준알고리즘] 2263번: 트리의 순회-C++ (tistory.com)

[백준알고리즘] 2263번: 트리의 순회-C++

 

처음 제출했을 때, 시간 초과가 발생했는데 이것도 이전에 '트리의 순회' 문제를 풀었을 때와 동일한 문제가 있었다.

---

문제 풀이

이전 '트리의 순회'와 다른 점은 한 가지로 볼 수 있다.

• 테스트 케이스마다 트리의 크기가 100,000에서 1,000으로 줄었으며, 그만큼 시간제한이 5초에서 1초로 줄었다.

 

그 외의 모든 것은 동일하다. 전위 순회법과 중위 순회법이 주어지면, 후위 순회법을 출력하면 된다. 이전과 마찬가지로 list를 넘겨주는 방식으로 문제를 풀었다가 시간 초과가 발생했다. 테스트 케이스가 줄었기 때문에 충분히 가능할 줄 알았는데, 시간이 그만큼 많이 줄어든 것을 파악하지 못했었다.

시간 초과가 발생해 다시 인덱스를 사용하는 방식으로 문제를 풀었다.

 

같은 문제를 풀어서, 거의 내용의 결은 같다. 다만 약간의 구조적 변경만 있었다.

왼쪽 자식 트리와 오른쪽 자식 트리를 분리해가며 분할 정복을 적용했다. 왼쪽 자식 트리와 오른쪽 자식 트리를 확인하는 방법은 '트리의 순회' 문제를 풀 때 적어두었기 때문에 생략한다.

#include <cstdio>
#include <vector>
#include <algorithm>

struct RANGE_st {
	RANGE_st(const size_t siStart, const size_t siEnd) : siStartIndex(siStart), siEndIndex(siEnd) {};
	inline size_t length() const {
		return siEndIndex - siStartIndex;
	}

	size_t siStartIndex;
	size_t siEndIndex;
};

std::vector<int> vecPreOrder;
std::vector<int> vecInOrder;

std::vector<int> inputTree(const int iSize);
std::vector<int> convertToPostOrder(const RANGE_st &rangePreOrder, const RANGE_st &rangeInOrder);

int main(void) {
	int iTestCase = 0;
	::scanf("%d", &iTestCase);

	for ( int iCase = 0; iCase < iTestCase; ++iCase ) {
		int iNode = 0;
		::scanf("%d", &iNode);
		
		vecPreOrder = inputTree(iNode);
		vecInOrder = inputTree(iNode);
		std::vector<int> vecPostOrder = convertToPostOrder(RANGE_st(0, vecPreOrder.size()), RANGE_st(0, vecInOrder.size()));

		for ( int iVal : vecPostOrder ) {
			printf("%d ", iVal);
		}
		printf("\n");
	}

	return 0;
}

std::vector<int> inputTree(const int iSize) {
	std::vector<int> vecTree;
	for ( int iCount = 0; iCount < iSize; ++iCount ) {
		int iVal = 0;
		scanf("%d", &iVal);
		vecTree.push_back(iVal);
	}
	return vecTree;
}

std::vector<int> convertToPostOrder(const RANGE_st &rangePreOrder, const RANGE_st &rangeInOrder) {
	const size_t siTreeSize = rangePreOrder.length();
	if ( 1 == siTreeSize ) {
		const int iRootVal = vecPreOrder[rangePreOrder.siStartIndex];
		return std::vector<int>(1, iRootVal);
	}
	else if ( 0 >= siTreeSize ) {
		return std::vector<int>();
	}

	const int iRootVal = vecPreOrder[rangePreOrder.siStartIndex];

	size_t siLeftChildSize = 0;
	for ( size_t siIndex = rangeInOrder.siStartIndex; siIndex < rangeInOrder.siEndIndex && iRootVal != vecInOrder[siIndex]; ++siIndex ) {
		++siLeftChildSize;
	}
	size_t siRightChildSize = siTreeSize - siLeftChildSize - 1;

	RANGE_st rangePreOrderLeftChild(rangePreOrder.siStartIndex + 1, 
									rangePreOrder.siStartIndex + 1 + siLeftChildSize);
	RANGE_st rangePreOrderRightChild(rangePreOrder.siStartIndex + 1 + siLeftChildSize,
									 rangePreOrder.siEndIndex);
	RANGE_st rangeInOrderLeftChild(rangeInOrder.siStartIndex,
								   rangeInOrder.siStartIndex + siLeftChildSize);
	RANGE_st rangeInOrderRightChild(rangeInOrder.siStartIndex + siLeftChildSize + 1,
									rangeInOrder.siEndIndex);

	std::vector<int> vecPostOrderLeftChild;
	if ( 0 < siLeftChildSize ) {
		vecPostOrderLeftChild = convertToPostOrder(rangePreOrderLeftChild, rangeInOrderLeftChild);
	}
	std::vector<int> vecPostOrderRightChild;
	if ( 0 < siRightChildSize ) {
		vecPostOrderRightChild = convertToPostOrder(rangePreOrderRightChild, rangeInOrderRightChild);
	}

	std::vector<int> vecPostOrder;
	for ( int iVal : vecPostOrderLeftChild ) {
		vecPostOrder.push_back(iVal);
	}
	for ( int iVal : vecPostOrderRightChild ) {
		vecPostOrder.push_back(iVal);
	}
	vecPostOrder.push_back(iRootVal);

	return vecPostOrder;
}