[백준알고리즘] 5639번: 이진 검색 트리 -C++

[백준알고리즘] 5639번: 이진 검색 트리 -C++

5639번: 이진 검색 트리 (acmicpc.net)

5639번: 이진 검색 트리

생각보다 애를 먹었다. 처음에 list 자료형을 이용해 splice 함수로 이리저리 preorder를 postorder로 바꾸려고 시도해봤다. 동작은 하는 것 같으나, 시간 초과/메모리 초과가 발생해 고민을 많이 했다.

 

그러다가 배열을 쓰는게 훨씬 빠르다는 것을 보고, 배열과 인덱스를 이용해 처리하도록 변경했다.

---

문제 풀이

트리 탐색 방법은 전위순회/중위순회/후위순회가 있다. 같은 트리를 읽는 방법이 3가지가 있는 것인데, 읽는 순서는 아래와 같다.

• 전위 순회(preorder) : 루트 노드 - 왼쪽 CHILD - 오른쪽 CHILD
• 중위 순회(inorder) : 왼쪽 CHILD - 루트 노드 - 오른쪽 CHILD
• 후위 순회(postorder) : 왼쪽 CHILD - 오른쪽 CHILD - 루트 노드

 

딱 봐도 알겠지만, 루트 노드의 위치에 따라 전위/중위/후위로 나뉜다.

 

이번 문제는 전위 순회를 후위 순회로 바꾸는 문제다. 간단하게는 루트 노드 위치만 맨 뒤로 옮기면 될 것 같지만, 주어진 트리가 '이진 트리'라면 생각보다 코드로 짜기에는 어려울 수 있다. 그래도 문제에서 주어진 다음 조건들 덕분에, 항상 '이진 탐색 트리'로 주어지기 때문에 나름 쉽게 풀 수 있게 된 문제다.

• 노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브 트리도 이진 검색 트리이다.

 

각 서브 트리마다 전위 순회 표기를 후위 순회 표기로 변경하는 방법으로 처리했다.

 

서브 트리의 범위를 넘겨주었고, 그중 가장 첫 번째 노드는 루트 노드로 인식하면 된다. 그리고 서브 트리의 범위 중에서 루트 노드보다 가장 먼저 큰 값이 나온 위치가 오른쪽 서브 트리의 시작 위치다. 만약, 오른쪽 서브 트리 시작 위치가 없다면 오른쪽 서브 트리가 없는 것이다.

 

왼쪽 서브 트리는 기본적으로 루트 노드 바로 다음부터 주어진다. 그리고 오른쪽 서브 트리 직전까지가 왼쪽 서브 트리의 범위다. 하지만, 오른쪽 서브 트리가 없을 수도 있고, 왼쪽 서브 트리가 없을 수도 있다는 것을 고려해야 한다.

 

위의 각 서브 트리에 대한 고려사항을 주의하면 나머지는 코드로 쉽게 확인이 가능하지 않을까 싶다.

#include <cstdio>

void printPreorderToPostorder();
void inputPreorder();
void convertPreorderToPostorder(int iStartIndex, int iEndIndex);
void pushNode(const int iNode);
int findRightChildTreeStartIndex(const int iStartIndex, const int iEndIndex);
int findLeftChildTestStartIndex(const int iStartIndex, const int iRightChildIndex);
void printPostorder();

int iTreeSize = 0;
int arrPreorder[10001] = { 0, };
int arrPostorder[10001] = { 0, };

int iPostIndex = 1;

int main(void) {
	printPreorderToPostorder();

	return 0;
}

void printPreorderToPostorder() {
	inputPreorder();
	convertPreorderToPostorder(1, iTreeSize);
	printPostorder();
}

void inputPreorder() {
	int iIndex = 1;
	int iNode = 0;

	while (EOF != scanf("%d", &iNode)) {
		arrPreorder[iIndex++] = iNode;
	}

	iTreeSize = iIndex - 1;
}

void convertPreorderToPostorder(int iStartIndex, int iEndIndex) {
	int iRootNode = arrPreorder[iStartIndex];

	// LEAF NODE
	if (iStartIndex == iEndIndex) {
		pushNode(iRootNode);
		return;
	}

	int iRightChildIndex = findRightChildTreeStartIndex(iStartIndex, iEndIndex);
	int iLeftChildIndex = findLeftChildTestStartIndex(iStartIndex, iRightChildIndex);

	// LEFT CHILD
	if (-1 < iLeftChildIndex) {
		if (-1 < iRightChildIndex) {
			convertPreorderToPostorder(iLeftChildIndex, iRightChildIndex - 1);
		}
		else {
			convertPreorderToPostorder(iLeftChildIndex, iEndIndex);
		}
	}
	// RIGHT CHILD
	if (-1 < iRightChildIndex) {
		convertPreorderToPostorder(iRightChildIndex, iEndIndex);
	}
	// ROOT NODE
	pushNode(iRootNode);
}

void pushNode(const int iNode) {
	arrPostorder[iPostIndex++] = iNode;
}

int findRightChildTreeStartIndex(const int iStartIndex, const int iEndIndex) {
	const int iRootNode = arrPreorder[iStartIndex];
	for (int iIndex = iStartIndex + 1; iIndex <= iEndIndex; ++iIndex) {
		if (iRootNode < arrPreorder[iIndex]) {
			return iIndex;
		}
	}

	return -1;
}

int findLeftChildTestStartIndex(const int iStartIndex, const int iRightChildIndex) {
	if (-1 == iRightChildIndex || iStartIndex + 1 < iRightChildIndex) {
		return iStartIndex + 1;
	}

	return -1;
}

void printPostorder() {
	for (int iIndex = 1; iIndex <= iTreeSize; ++iIndex) {
		printf("%d\n", arrPostorder[iIndex]);
	}
}