38 inversion sequence

배열의 크기 n 과 배열에 들어갈 값 n개의 정수를 입력받는다. 

입력예제 

8

5 3 4 0 2 1 1 0

각 입력값은 순서대로 1부터 n까지 각 자리수의 왼쪽에 자신보다 큰 값의 개수이다.

이런 입력값이 주어졌다면 1은 자신의 왼쪽에 자신보다 큰 수가 5개 있다.

2는 왼쪽에 자신보다 큰 수가 3개 있다.

3은 왼쪽에 자신보다 큰 수가 4개 있다.

inversion sequence가 주어지면 이것으로 원래 배열의 위치(original sequence)를 찾는 문제이다.

 

 

8은 자기자신보다 큰 수가 없다. inversion sequence의 배열원소에 접근해서 값을 count에 넣고 count횟수만큼 삽입정렬을 반복하면 된다. 중요한 점은 배열의 뒤쪽부터 접근해서 문제를 해결해야 한다.

inversion sequence 7의 값은 1이므로 7의 왼쪽에 7보다 큰 값의 개수는 1이다.삽입정렬을 1번 반복한다.

마찬가지로 6의 값은 1이므로 삽입정렬을 1회 반복한다.

inversion sequence 5의 값은 2이므로 삽입정렬을 2회 반복한다.

이런식으로 count를 세서 삽입정렬을 각 자리수에 반복해주면 original sequence 배열을 구할 수 있게 된다.

#include<stdio.h>
int inversionSequence[20];
int originalSequence[20];
int main(){
	int n, i, j, z, isDigit, count, temp;
	scanf("%d", &n);
	
	for(i = 0; i < n; i++)
	{
		scanf("%d", &isDigit);
		inversionSequence[i] = isDigit;
	}
	
	for(i = n-1; i >= 0 ; i--)
	{
		
		count = inversionSequence[i];
		temp = i+1;
		
		for(j = 0; j < count; j++)
		{
				originalSequence[i+j] = originalSequence[i+1+j];
		} 
		
		originalSequence[i+count] = temp;

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