[백준/BOJ] 백준 1777번 : 순열복원

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

1777번: 순열복원

number_check에 숫자의 자리가 채워진 위치는 0으로 체크하고 자리가 채워지지 않은 위치는 1로 체크하여 이것을 합 세그먼트 트리로 만든다. 그리고 큰 숫자부터 자리를 찾아가면서 해당 숫자보다 뒤에 나오면서 해당 숫자보다 작은 수의 개수는 number_check에서 뒤에 1로 채워진 개수가 몇 개인지 확인하는 이분 탐색을 통해 자리를 찾으면서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> input_list(100001);
vector<int> number_check(100001, 1); //숫자가 들어간 위치는 0으로 체크
vector<int> sgmtt(100001 * 4);
vector<int> output(100001);

int MakeSgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
		return sgmtt[here] = number_check[range_right];

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return sgmtt[here] = MakeSgmtt(left_child, range_left, range_mid) + MakeSgmtt(right_child, range_mid + 1, range_right);
}

int UpdateSgmtt(int here, int range_left, int range_right, int update_index)
{
	if (range_left == range_right && range_right == update_index)
		return sgmtt[here] = number_check[update_index];

	if (update_index < range_left || range_right < update_index)
		return sgmtt[here];

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return sgmtt[here] = UpdateSgmtt(left_child, range_left, range_mid, update_index) + UpdateSgmtt(right_child, range_mid + 1, range_right, update_index);
}

int QuerySgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_right < range_left || range_right < find_left)
		return 0;

	if (find_left <= range_left && range_right <= find_right)
		return sgmtt[here];

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return QuerySgmtt(left_child, range_left, range_mid, find_left, find_right) + QuerySgmtt(right_child, range_mid + 1, range_right, find_left, find_right);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	MakeSgmtt(0, 1, n);

	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		input_list[i] = input;
	}

	//큰 숫자 부터 자리 찾기
	for (int i = n; i >= 1; i--)
	{
		//i보다 뒤에 나오면서 i보다 작은 수의 개수는 number_check에서 해당숫자 뒤에 1로 채워진 개수가 몇개인지 확인한다(0으로 채워진것은 해당 숫자보다 큰수(i가 큰수부터 확인하므로))
		int left = 1;
		int right = n;
		int result = -1;

		while (left <= right)
		{
			int mid = (left + right) / 2;

			if (QuerySgmtt(0, 1, n, mid, n) >= input_list[i] + 1)
			{
				result = mid;

				left = mid + 1;
			}

			else
			{
				right = mid - 1;
			}
		}

		output[result] = i; //숫자 i는 result위치에 들어가야 된다
		number_check[result] = 0; //들어간 위치는 0으로 표시
		UpdateSgmtt(0, 1, n, result);
	}

	for (int i = 1; i <= n; i++)
		cout << output[i] << " ";

	return 0;
}