[Javascript] BOJ_2263. 트리의 순회

🦍 문제

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

 

---

🐈 문제 풀이

1. 무엇을 구해야 할까?

이진트리의 중위 순회와 후위 순회 결과값이 주어졌을 때, 이를 바탕으로 전위 순회 결과를 구해야 한다.

2. 어떻게 구해야 할까?

중위 순회, 후위 순회 결과에서 규칙을 찾아내, 재귀적으로 탐색하게끔 하면 전위 순회를 구할 수 있다.

3. 특별히 고려해야 할 사항은?

 주어지는 n 값(노드의 개수)이 최대 100,000이다. Node.js 환경에서는 콜스택의 최대 크기가 대략 10,000이므로, 재귀함수를 통해 풀이하면 Maximum call stack size exceeded 에러를 만날 수 있다. 따라서 스택을 활용해 재귀함수를 활용한 것과 같은 동작을 하게끔 해야 한다.

---

중위 순회, 후위 순회로부터 전위 순회 결과를 얻어내기 위한 접근법

위와 같은 트리가 존재할 때, 이 트리의 중위 순회와 후위 순회 결과는 위와 같다.

 

재귀적으로 전위 순회를 얻어내려면, 각 단계에서의 root와 해당 root로부터 파생되는 양쪽의 서브트리를 파악해야 한다.

 

첫 단계에서의 root 노드를 파란색으로 표시해 보면 어느 정도 규칙을 찾을 수 있다.

후위 순회 결과에서 가장 뒤쪽에 위치한 1이 바로 root임을 알 수 있고,

중위 순회에서는 root인 1을 기준으로 잡았을 때, 좌/우로 각각 서브트리가 위치함을 알 수 있다.

 

위쪽의 이미지에서 해당 단계에서 각각 유효한 중위 순회, 후위 순회의 범위도 표시해 봤다.

다음 단계로 넘어가며 양 쪽 서브트리를 탐색하는 모습도 그려보자면 다음과 같다.

각각 좌측 서브트리, 우측 서브트리에 대한 모습을 표현해 봤다.

 

위 이미지에서도 확인이 가능하듯, 후위 순회에서 유효한 범위 내 가장 뒤쪽에 있는 노드가 root를 가리킴을 알 수 있으며, 중위 순회에서는 해당 root를 기준으로 좌, 우로 서브트리가 형성돼있음을 알 수 있다.

 

또한, 해당 유효 범위를 설정해 나감에 있어 중위 순회가 가지는 범위와 후위 순회가 가지는 범위가 상이함을 알 수 있다.

- 중위 순회 결과
- 후위 순회 결과
- 중위 순회에서의 범위를 나타낼 양 끝의 두 인덱스
- 후위 순회에서의 범위를 나타낼 양 끝의 두 인덱스

 

결과적으로 위 네 가지 정보를 토대로 문제를 해결할 수 있다.

 

여기서 가장 애를 먹었던 부분은 범위를 좁혀나감에 있어 양 끝 인덱스를 어떻게 설정해줘야 할지였는데, 머리로 쉽사리 그려지지 않아 그림을 그려가며 풀이했었다.

---

🐕‍🦺 소스 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

function solution() {
	let idx = 0;
	const N = Number(input[idx++]);

	const inOrder = input[idx++].split(' ').map(Number);
	const postOrder = input[idx++].split(' ').map(Number);

	const answer = [];

	const stack = [];
	stack.push([0, N - 1, 0, N - 1]); // inL, inR, postL, postR

	while (stack.length !== 0) {
		let [inL, inR, postL, postR] = stack.pop();
		if (inL > inR || postL > postR) {
			continue;
		}

		const root = postOrder[postR];
		answer.push(root);

		let rootIndex;
		for (let i = inL; i <= inR; i++) {
			if (inOrder[i] === root) {
				rootIndex = i;
				break;
			}
		}

		stack.push([rootIndex + 1, inR, postL + rootIndex - inL, postR - 1]);
		stack.push([inL, rootIndex - 1, postL, postL + rootIndex - 1 - inL]);
        
        // 재귀함수가 아닌 스택을 활용하고 있으므로 stack에 push해주는 순서도 고려해야한다.
        // 스택에 먼저 들어간 값이 나중에 나옴을 인지하고, 전위 순회를 위해 우측 서브트리에 대한
        // 값을 우선적으로 push해줬다.
        // 이는 재귀 함수를 활용할때와는 반대의 순서를 가진다.
	}

	return answer.join(' ');
}

console.log(solution());

---

---

🐖 Think

- 기존에 유사한 문제를 slice를 활용해 잘라진 배열을 만들어나가 쉽게 풀이했던 경험이 있었는데, 계속해서 생성되는 배열에 대한 공간복잡도를 고려하지 못했었다. 위와 같은 방법을 통하면 메모리적으로 최적화가 가능함을 느낄 수 있었다.