[백준 2605: 줄 세우기][C++]

문제 설명

학생들이 한 줄로 줄을 선 후, 첫 번째 학생부터 차례로 번호를 뽑는다. 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다. 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다. 0번을 뽑으면 그 자리에 그대로 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다. 세 번째로 줄을 선 학생은 0, 1 또는 2 중 하나의 번호를 뽑는다. 그리고 뽑은 번호만큼 앞자리로 가서 줄을 선다. 마지막에 줄을 선 학생까지 이와 같은 방식으로 뽑은 번호만큼 앞으로 가서 줄을 서게 된다. 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.

입력:

첫째 줄에는 학생의 수가 주어지고 둘째 줄에는 줄을 선 차례대로 학생들이 뽑은 번호가 주어진다. 학생의 수가 100 이하이고, 학생들이 뽑는 번호는 0 또는 자연수이며 학생들이 뽑은 번호 사이에는 빈 칸이 하나씩 있다.

출력:

학생들이 처음에 줄을 선 순서대로 1번부터 번호를 매길 때, 첫째 줄에 학생들이 최종적으로 줄을 선 순서를 그 번호로 출력한다. 학생 번호 사이에는 한 칸의 공백을 출력한다.

 

코드

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

int main(void) {
	int people;
	vector<int> n = {0};
	vector<int> student = {0};

	cin >> people;	//학생 수 입력
	for (int i = 1,a=0; i <= people; i++) {
		student.push_back(i);	//학생이 서있는 배열 초기화. 1번이 첫번째, 2번이 2번째....
		cin >> a;
		n.push_back(a);		//학생이 뽑은 번호 입력
	}
	for (int i = 1; i <=people; i++) {
		int a = i;
		int push_num = i-n[i]; //뽑은 번호만큼 '앞으로' 이동했을 때의 학생의 위치
		student.insert(student.begin()+push_num, a); // 학생을 앞으로 이동시키고, 옮긴 위치 이후 학생 순서 뒤로 밀기
	}
	for (int i = 1; i <= people; i++) {
		cout << student[i] << " "; // 공백으로 구분하여 학생 출력
	}	
	return 0;
}

문제 풀이

학생 수를 입력받고 그 학생이 이동한 후의 위치를 구하여 그 위치에 학생을 이동시킨다. 그 후 기존의 학생 배열이 업데이트되고, 그 업데이트된 배열을 통해 다음 번호의 학생을 같은 방식으로 이동시킨다. vector에서의 insert를 이용하여 반복문을 돌려주면, 기존 번호의 index를 뒤로 한칸씩 밀어내는 코드를 작성하지 않아도 되기에 문제를 쉽게 풀 수 있다.

​

어려웠던 점, 개선점

vector와 insert를 처음 사용해 보는 것이어서 에러가 계속 발생했다. 아직 C++을 제대로 공부하지 않아서인 것 같은데, 더 꼼꼼히 공부해야겠다...

 

원본 링크 : https://blog.naver.com/ahtnwl1004/222724300462