[인프런 C++] 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가 주어졌을 때, 원래의 수열을 출력하는 프로그램을 작성하세요.

 

🍧 입력

8

5 3 4 0 2 1 1 0

 

🍧 출력

4 8 6 2 5 1 3 7

 

🍧 1트 (강의 풀이)

가장 큰 값부터 처리한다.

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

int main(void){
	freopen("input.txt", "rt", stdin);
	
	int n, pos;
	cin >> n;
	vector<int> is(n+1), os(n+1);
	
	for(int i = 1; i <= n; ++i){
		cin >> is[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] << ' ';
	}
	
	return 0;
}