1083번: 소트

문제링크: 1083번: 소트

문제

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

설명

첫번째 인덱스부터 마지막 인덱스까지 옮길 수 있는 범위를 계산하고 가장 큰 숫자를 해당 인덱스로 옮기면 쉽게 풀수 있는 문제이다.

정렬이 종료되는 순간은 마지막인덱스를 다 탐색했거나 S가 0이 되는 경우가 있는데 이 두가지 경우를 신경쓰면서 구현하면 해결할 수 있는 문제이다.

코드

#include <iostream>
#include <vector>
#define endl '\n'

using namespace std;

void swap(vector<int>& v, int a, int b) {
	int tmp = v[b];
	for (int i = b; i > a; --i) {
		v[i] = v[i - 1];
	}
	v[a] = tmp;
}

void solve() {
	int N, S;
	cin >> N;
	vector<int> v;
	v.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> v[i];
	}
	cin >> S;

	for (int start = 0; start < N && S>0; ++start) {
		int idx = start;
		for (int end = start; end < N && end <= start + S; ++end) {
			if (v[idx] < v[end]) idx = end;
		}
		swap(v, start, idx);
		S -= idx - start;
	}

	for (int a : v) {
		cout << a << ' ';
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
	solve();
	return 0;
}