[1777] 순열복원

• 난이도: 하
• 입력: 테스트 케이스 N, N개의 원소를 가진 inversion sequence 
• 출력: inversion sequence에 대응하는 순열을 출력한다.
• 소스

#include <iostream>    
#include <vector>
#define MAX 100000
using namespace std;


int main(){
	int N;
	cin >> N;
	int inversion[MAX];
	vector<int> origin;
	for (int i = 0; i < N; i++)
		cin >> inversion[i];
	for (int j = 0; j < N; j++){
		if (inversion[j] == 0) origin.push_back(j + 1);
		else{
			vector<int>::iterator pos = origin.end();
			pos -= inversion[j];
			origin.insert(pos, j + 1);
		}
	}
	for (int i = 0; i < N; i++)
		cout << origin[i] << " ";

	return 0;
}

• 소스 설명:

inversion sequence에 입력된 값을 vector를 이용해서 1~N까지 차례대로 추가하였다. 추가하는 방법은 i번째 원소의 값만큼 origin의 end부터 떨어진 장소에 i를 추가하는 방식이다. 만약 0일 경우, push_back을 사용하였는데, 없어도 아무런 문제가 없을 것으로 예상된다. linked list나 array를 사용했을 때는 시간초과가 떴지만 vector를 이용하니 성공하였다.

• 참고사이트: https://www.acmicpc.net/problem/1777