BOJ 1849 순열

문제

1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라.

입력

첫째 줄에 수열 원소의 개수 (1 ≤ N ≤100,000)이 주어진다. 그리고 두 번째 줄부터 N+1 번째 줄까지 차례로 A[i]가 주어진다.

출력

N개의 줄에 걸쳐서 수열을 출력한다. (i번째 줄에는 i번째 원소를 의미한다)

예제 입력 1

8 5 0 1 2 1 2 0 0

예제 출력 1

2 7 3 5 4 1 8 6

풀이

이 문제는 세그먼트 트리와 파라매트릭 바이너리 서치를 이용한 문제이다.

 

원래 수열을 구하려면 맨 앞에서부터 하나하나 찾는 방법으로 원래 수열을 구할 수 있다. 우선 길이가 N인 빈 배열 B를 만든다. 그 후 i번째 수는 B의 맨 앞에 A[i]개 만큼의 빈칸을 남겨 놓고 그 뒤에 수 i를 B에 넣으면 된다. (아래 그림 참조)

1

앞에 빈칸 5칸을 남기고 1을 배정함

2

1

앞에 빈칸 0칸을 남기고 2을 배정함

2

3

1

앞에 빈칸 1칸을 남기고 3을 배정함

2

3

4

1

앞에 빈칸 2칸을 남기고 4을 배정함

2

3

5

4

1

앞에 빈칸 1칸을 남기고 5을 배정함

2

3

5

4

1

6

앞에 빈칸 2칸을 남기고 6을 배정함

2

7

3

5

4

1

6

앞에 빈칸 0칸을 남기고 7을 배정함

2

7

3

5

4

1

8

6

앞에 빈칸 0칸을 남기고 8을 배정함

 

이때 이 위치를 찾는데 logN 정도의 시간복잡도로 찾으면 주어진 시간 내에 해결할 수 있다. 이 과정에서 세그먼트 트리를 사용한다. 우선 세그먼트 트리를 사용해 구간 [x, y]에서 B[i]가 비어있는 갯수를 구할 수 있게 한다. 이때, a<b일때 [1, a]에서 B[i]가 비어있는 갯수는 [1, b]에서보다 같거나 적으므로 이진탐색을 이용하여 구할 수 있다.

 

구현 시 N이 10만 이하이지만 리프 노드가 N개인 세그먼트 트리를 구현해야 하므로 트리 배열의 크기를 넉넉하게 잡아야 한다.

 

소스코드

#include <stdio.h>
#include <math.h>

#define MAX 400010

int tree[MAX];
int l[MAX];
int r[MAX];
int use[MAX];
int ans[MAX];

int s; //리프노드의 갯수

void init(int x) //초기화 함수
{
	if (s <= x && x < s * 2)
	{
		l[x] = x - s + 1;
		r[x] = x - s + 1;
		return;
	}
	init(x * 2);
	init(x * 2 + 1);

	l[x] = l[x * 2];
	r[x] = r[x * 2 + 1];
}

void update(int x) //x번째 값을 채움
{
	if (!x)
	{
		return;
	}
	tree[x]++;
	update(x / 2);	
}

int sumquery(int loc, int x, int y) //쿼리 함수, x~y간의 합을 구함
{
	if (x == y)
	{
		return tree[x + s - 1];
	}
	if (l[loc] == x && r[loc] == y)
	{
		return tree[loc];
	}
	if (r[loc * 2] >= y)
	{
		return sumquery(loc * 2, x, y);
	}
	if (l[loc * 2 + 1] <= x)
	{
		return sumquery(loc * 2 + 1, x, y);
	}
	return sumquery(loc * 2, x, r[loc * 2]) + sumquery(loc * 2 + 1, l[loc * 2 + 1], y);
}

int findloc(int x, int N) //적당한 위치를 찾아주는 함수
{
	int start, end, mid;
	start = 1, end = N;

	while (end > start) //이진 탐색
	{
		mid = (start + end) / 2;
		if (mid - sumquery(1, 1, mid) - 1 >= x)
		{
			end = mid;
		}
		else
		{
			start = mid + 1;
		}
	}

	while (use[end] == 1) end++; //이미 그 위치에 다른 값이 있을 경우 end값을 증가시킴
	return end;
}

int main()
{
	int N;
	scanf("%d", &N);

	s = 1 << (int)ceil(log2(N));

	init(1);

	int i;
	int a;
	int loc;
	
	for (i = 1; i <= N; i++)
	{
		scanf("%d", &a);
		update((loc = findloc(a, N)) + s - 1);
		use[loc] = 1;
		ans[loc] = i; //설명에 있는 B배열
	}

	for (i = 1; i <= N; i++)
	{
		printf("%d\n", ans[i]);
	}

	return 0;
}