백준 1083번 소트 C++

출처 : https://www.acmicpc.net/problem/1083

 

1. 배열을 탐색하면서 가장 큰 값을 찾는데, 순회 도중 인덱스가 s를 넘어가면 탐색을 중지한다. (인덱스가 s를 넘어서는 가장 큰 값을 찾았다고 해도 인덱스만큼 옮길 수 없기 때문에 그 수를 맨 앞으로 옮길 수 없다.)

 

2. 찾은 수는 맨 앞으로 옮길 수 있는 수 중에서 가장 큰 수이다. 맨 앞으로 옮기면 그 위치에 고정될 것이고, 앞으로 옮기는 데에 비용이 들기 때문에 배열에서 찾은 수를 지우고 새로운 벡터에 찾은 수를 넣는다.

 

3. 이론상으로는 앞으로 옮긴 것이기 때문에 s에서 찾은 수의 인덱스를 빼준다.

 

4. s가 0이 되거나 이미 모든 수가 정렬이 되어있으면 앞에서부터 차례대로 2에서 만든 벡터에 값을 넣어준다.

 

5. 새로운 벡터의 원소들을 출력한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, s;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	vector<int> nums(n);
	vector<int> ans;
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	cin >> s;
	while (true) {
		int max_val = -1;
		int max_idx = 0;
		bool isSort = true;
		int lastVal = 0;
		for (int i = 0; i < static_cast<int>(nums.size()); i++) {
			if (lastVal < nums[i]) isSort = false;
			lastVal = nums[i];
			if (nums[i] > max_val) {
				max_val = nums[i];
				max_idx = i;
			}
			if (i == s) break;
		}
		if (isSort || s == 0) {
			for (int i = 0; i < static_cast<int>(nums.size()); i++) {
				ans.push_back(nums[i]);
			}
			break;
		}
		nums.erase(nums.begin() + max_idx);
		ans.push_back(max_val);
		s -= max_idx;
	}
	for (auto a : ans) {
		cout << a << " ";
	}
};