백준2605 줄 세우기

작성일 | In

문제 링크

  • http://icpc.me/2605

문제 출처

  • 2004 지역 본선 초등2

시간복잡도

  • O(n2)

풀이

STL의 vector컨테이너에서 지원하는 find, erase, insert 메소드를 이용하여 쉽게 풀 수 있습니다.
물론, 일반적인 배열에서 직접 구현해도 무방합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

typedef vector<int>::iterator iter;

int main(){
	int n; scanf("%d", &n);
	vector<int> v(n+1);
	for(int i=1; i<=n; i++) v[i] = i;
	for(int i=1; i<=n; i++){
		int t; scanf("%d", &t);
		iter it = find(v.begin(), v.end(), i);
		iter a = it;

		while(t--) a--;
		v.erase(it);
		v.insert(a, i);
	}

	for(int i=1; i<=n; i++) printf("%d ", v[i]);
}