백준 2263, 트리의 순회

문제

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

풀이

곰곰히 생각하다가 분할 정복으로 풀 수 있다는 것을 보고 L V R로 각각 따로 나눠서 분할 정복하면 쉽게 풀렸다.

다만 나는 inorder의 위치를 찾을때 반복문으로 찾았는데, 위치는 고정되어 있고 값은 고유하므로(값도 작음) 해당 값을 가지는 위치를 미리 배열에 저장해두면 나처럼 1000ms 걸리는게 아니라 30ms정도에 처리할 수 있다.

실수

• 구간 설정을 계속 잘못해서 20분을 까먹은 것 같다.
• 풀이 방법을 보고 떠올랐다. 풀이를 생각하는 방법을 잘 익혀야 겠다.

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector<int> inorder(110000, 0);
vector<int> postorder(110000, 0);

int n;

void dq(int in_s, int in_e, int post_s, int post_e) {

	if (in_e < in_s || post_e < post_s)
		return;

	if (!(0 <= in_s && in_e < n && 0 <= post_s && post_e < n))
		return;

	if (in_s == in_e) {

		printf("%d ", inorder[in_s]);
		return;

	}

	int in_v, post_v;

	post_v = post_e;

	for (int i = in_s; i <= in_e; i++) {

		if (postorder[post_v] == inorder[i]) {

			in_v = i;
			break;

		}

	}

	printf("%d ", postorder[post_v]);

	dq(in_s, in_v - 1, post_s, post_s + in_v - 1 - in_s);
	dq(in_v + 1, in_e, post_s + in_v - in_s, post_e - 1);


}

int main() {

	int temp;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {

		scanf("%d", &temp);

		inorder[i] = temp;

	}

	for (int i = 0; i < n; i++) {

		scanf("%d", &temp);

		postorder[i] = temp;

	}

	dq(0, n - 1, 0, n - 1);

	return 0;

}