[C++] 백준 1083번 소트

정렬 문제입니다.

연속된 두개의 원소만 변경할 수 있다고 되어있는 부분을 통해 버블정렬을 생각할 수 있습니다.
내림차순으로 버블정렬을 하는데 이동횟수가 정해져있을때 가장 왼쪽값들이 크도록 하여야 합니다.

가장왼쪽부터 정렬을 하고, 횟수가 남아있으면 다음 수를 정렬합니다.
정렬을 할때도 이동횟수보다 멀리 있으면 그 전에 있는 값들중 가장 큰 값으로 정렬을합니다.

정렬은 벡터를 통해서, erase로 큰값을 지우고, 지운 값을 정렬중인 위치에 insert를 통해서 넣습니다.

 

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

int main(int argc, char *argv[])
{
	int n;
	int change;
	int change_index;
	int change_max;
	int next = 0;
	int num;
	vector<int> arr;

	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> num;
		arr.push_back(num);
	}
	cin >> change;

	while (change != 0 && next != n) {
		change_index = next;
		change_max = arr[change_index];

		for (int i = next; i < n; ++i) {
			if (arr[i] > change_max && i - next <= change) {
				change_index = i;
				change_max = arr[i];
			}
		}
		
		arr.erase(arr.begin() + change_index);
		arr.insert(arr.begin() + next, change_max);
		change -= change_index - next;
		++next;
	}

	for (int i = 0; i < n; ++i) {
		cout << arr[i] << " ";
	}
	cout << endl;

	return 0;
}