[백준][C++] 1083: 소트

문제 링크: https://www.acmicpc.net/problem/1083

 

버블소트를 약간 응용하는 문제입니다. swap 할 수 있는 횟수가 정해져 있는데요, 이 부분을 처리해줘야 합니다.

맨 앞자리부터 이 자리에 어떤 값을 올릴 수 있을지, swap 횟수가 되는 동안 옮길 수 있는 가장 큰 값을 골라서 앞으로 옮깁니다.

정렬이 다 되거나, swap 횟수가 다 떨어지면 정렬된 배열을 출력하면 됩니다.

 

옛날엔 문제에 명시는 되어있지 않은데, 테스트케이스가 여러개 들어올 수 있었다고 합니다.

지금은 테스트케이스가 쪼개져있어서 처리 안해줘도 됩니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int n;
	cin >> n;
	
	vector<int> v(n);
	for (auto& c : v)
		cin >> c;

	int s;
	cin >> s;

	int mx, idx;
	for (int i=0; i<n && s; ++i) {
		mx = idx = -1;
		for (int j=i, k=0; j<n && k<=s; ++j, ++k)
			if (mx < v[j]) {
				mx = v[j];
				idx = j;
			}

		for (int j=idx; j>i && s; --j, --s)
			swap(v[j], v[j - 1]);
	}

	for (auto& c : v)
		cout << c << ' ';
	cout << '\n';

	return 0;
}