[백준/BOJ] 백준 1849번 : 순열

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

1849번: 순열

작은 숫자부터(1부터) 해당 숫자의 위치를 찾았다. 해당 숫자 앞에 해당 숫자보다 큰 것의 개수가 a개 있다고 하면, 비어있는 자리들 중 a+1번째에 해당 숫자가 들어가야 된다 왜냐하면 채워져 있는 자리는 모두 해당 숫자보다 작은 숫자들이기 때문이다(작은 숫자부터 채우기 때문)

 

코드

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

int n;
vector<int> a(100000, 1); //[해당 위치] = (해당 위치가 비어있으면 : 1, 해당 위치가 비어있지 않으면 : 0) (처음에는 다 비어있으므로 1로 초기화)
vector<int> sgmtt(400000);
vector<int> output(100000);

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

	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] = a[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_left <= range_left && range_right <= find_right)
		return sgmtt[here];

	if (find_right < range_left || range_right < find_left)
		return 0;

	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, 0, n - 1);

	//숫자 i의 위치 찾기
	//작은수부터 위치를 찾는다
	for (int i = 1; i <= n; i++)
	{
		//i의 앞에는 i보다 큰것의 개수가 input개 있어야 한다
		//즉 비어있는 자리들중 input+1번째에 i가 들어가야 한다 (채워있는 자리는 모두 i보다 작은수들이다)
		//즉 비어있는 자리 input+1개를 찾아서 input+1번째에 i를 넣어야 된다
		int input;
		cin >> input;

		int left = 0;
		int right = n - 1;
		int result = -1;

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

			//0~mid 위치의 빈공간의 개수
			int empty_size = QuerySgmtt(0, 0, n - 1, 0, mid);

			if (empty_size >= input + 1)
			{
				result = mid;

				right = mid - 1;
			}

			//빈공간이 부족할때
			else
			{
				left = mid + 1;
			}
		}

		output[result] = i;
		a[result] = 0;
		UpdateSgmtt(0, 0, n - 1, result);
	}

	for (int i = 0; i < n; i++)
	{
		cout << output[i] << "\n";
	}

	return 0;
}