Inversion Sequence(38)

38. Inversion Sequence
1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다.
예를 들어 다음과 같은 수열의 경우
4 8 6 2 5 1 3 7
1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고,
2앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개,
3앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개......
따라서 4 8 6 2 5 1 3 7의 inversion sequence는 5 3 4 0 2 1 1 0 이 된다.
n과 1부터 n까지의 수를 사용하여 이루어진 수열의 inversion sequence가 주어졌을 때, 원래의 수열을 출력하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<100)이 주어지고, 두 번째 줄에는 inversion sequence가 숫자 사이에 한 칸의 공백을 두고 주어진다.
▣ 출력설명
오름차순으로 정렬된 수열을 출력합니다.
▣ 입력예제 1
8
5 3 4 0 2 1 1 0
▣ 출력예제 1
4 8 6 2 5 1 3 7

 

 

#include <iostream>

using namespace std;




int main(void)
{
	
	int n, arr[20],pos,cnt=0,arr2[20];
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	for (int i = 1; i <= n; i++)
	{
		cnt = 0;
		pos = 0;
		for (int j = 0; j < n; j++)
		{
			if (arr[j] == i)
				pos = j;
		}
		if (pos != 0)
		{
			for (int j = pos; j >= 0; j--)
			{
				if (arr[j] > i)
					cnt++;
			}
		}
		arr2[i-1] = cnt;
	}


	for (int i = 0; i < n; i++)
		printf("%d ", arr2[i]);
	return 0;
	
}

 

 

 

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




int main(void)
{
	
	int n, i, j, pos;

	cin >> n;
	vector<int> is(n + 1), os(n + 1);
	for (i = 1; i <= n; i++)
		cin >> is[i];
	for (i = n; i >= 1; i--)
	{
		pos = i;
		for (j = 1; j <= is[i]; j++)
		{
			os[pos] = os[pos + 1];
			pos++;
		}
		os[pos] = i;
	}
	for (int i = 1; i <= n; i++)
		printf("%d ", os[i]);
	return 0;
	
}

기존에 역으로 숫자가 카운트 된 것을 기준으로 원래의 배열을 만들어내야한다.

 

이 코드는 뒤에서부터 돌면서, 각 값이 있으면 그 값에 있는 카운트만큼 뒤로 미루면 된다.