[Algorithm] 38. 반전 수열(Inversion Sequence)

 

인트로

수열을 응용한 문제이다.

반전 수열(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가 숫자 사이에 한 칸의 공백을 두고 주어진다.

※ 출력 설명
원래의 수열을 차례대로 출력하시오.

입력

8
5 3 4 0 2 1 1 0

출력

4 8 6 2 5 1 3 7

코드 설명

두 가지 방법을 생각해볼 수 있다.

 

1) 숫자 1부터 시작해서 원래의 수열을 찾아가는 것

 

2) 마지막 숫자부터 시작해서 원래의 수열을 찾아가는 것

 

개인적으로 2)가 더 올바른 접근 방법 같다.

자신보다 큰 숫자가 N-1개 있는 숫자 1부터 자리를 찾아가는 것이 아니라,  

항상 자신 앞에 큰 숫자가 없는 숫자 N부터 자리를 잡아가는 것이 더 쉽다.

 

본 문제의 예시에서 [5, 3, 4, 0, 2, 1, 1, 0]

숫자 "7"의 Inversion Sequence가 1이라면 "7"은 무조건 "8"뒤에 있다는 결론을 내릴 수 있다. 

나아가 숫자 "6"은 "8"과 "7" 사이 어딘가에 있다는 결론을 내릴 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, pos;

	cin >> n;

	vector<int> is(n+1), os(n+1);

	for (int i = 1; i <= n; i++)
	{
		cin >> is[i];
		os[i] = i;
	}

	for (int i = n; i >= 1; i--)
	{
		pos = i;

		for (int j = 1; j <= is[i]; j++)
		{
			os[pos] = os[pos + 1];
			pos++;
		}
		os[pos] = i;
	}

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