# 순열을 이진트리로

# 문제

 

# 입력 및 출력

 

# 풀이

분할 정복으로 풀면 된다.

pair<int, int> p[1000] 은 순열의 수와 depth를 쌍으로 저장할 배열
visit[1000]은 해당 순열을 트리에 넣었는지 확인하는 배열

find_max_idx(int s, int e) 함수는 p배열의 index s ~ e 범위에서 가장 큰 값이 있는 인덱스를 리턴
rec(int s, int e, depth) 함수는 재귀적으로 돌면서 트리의 depth를 구하는 함수로 이미 트리에 있는 숫자가 들어오면 리턴

 

#include <fstream>
using namespace std;

ifstream fin("permutation.inp");
ofstream fout("permutation.out");

pair<int, int> p[1000];
int visit[1000];
int T, N;

// 최대값의 인덱스 리턴
int find_max_idx(int s, int e) {
	int midx = s;
	for (int i = s; i <= e; i++) {
		if (!visit[i] && p[midx].first < p[i].first) {
			midx = i;
		}
	}
	return midx;
}

// 분할 정복
void rec(int s, int e, int depth) {
	int midx = find_max_idx(s, e); // 최대값 인덱스 찾음
	if (visit[midx]) return; // 이미 트리에 있는 수면 리턴
	visit[midx] = 1; // 트리에 있다고 표시
	p[midx].second = depth; // 깊이 저장
	rec(s, midx - 1, depth + 1); // 왼쪽 서브트리
	rec(midx + 1, e, depth + 1); // 오른쪽 서브트리
}

// 출력
void print() {
	for (int i = 0; i < N; i++) {
		fout << p[i].second << " ";
	}
	fout << "\n";
}

int main() {
	fin >> T;
	while (T--) {
		fin >> N;
		for (int i = 0; i < N; i++) {
			fin >> p[i].first;
			p[i].second = 0; // 초기화
			visit[i] = 0; // 초기화
		}
		rec(0, N - 1, 0); 
		print();
	}
}

 

 

ez~