#include <iostream>
/*
단순한 정렬 문제가 아님(차례대로[인덱스처음부터] 비교하며 바꾸는 횟수가 아님) -> ex. 10 20 30 40 에 S가 2이면 20 30 10 40이 나오는 것이 아닌 30 10 20 40이 나와야 함
S만큼 교환 가능한 범위에서 최댓값을 가장 앞으로 가져오기 -> S<N 일때, 배열의 S번째까지 가장 앞으로 가져올 수 있음
1. 배열의 S번째까지 최댓값 탐색 후 위치(index) 저장
2. 해당 배열의 위치부터 탐색시작위치(i)까지 교환 반복
3. 교환 횟수를 S에서 빼주고 위 과정 반복
경우 1: S값이 배열의 크기(N)보다 작을 때
경우 2: S값이 배열의 크기(N)보다 클 때
*/
// using namespace std;
int main() {
int N, S, temp;
int A[50];
int i, j, max_num, max_idx = 0;
std::cin >> N;
for (int i = 0; i < N; i++)
std::cin >> A[i];
std::cin >> S;
for(i=0; i<N; i++){
if (S <= 0) break;
max_num = A[i]; // 탐색 시작하는 위치를 최댓값이라고 가정 후 최댓값 탐색 시작
max_idx = i;
for (j = i+1; j < N; j++) {
if (S-(j-i)>=0) { // S>N 일 경우 i는 이미 정렬이 되어있으므로 i를 빼주어야 함
if (max_num < A[j]) {
max_num = A[j];
max_idx = j;
}
}
}
for (int k = max_idx; k > i; k--) {
temp = A[k - 1];
A[k - 1] = A[k];
A[k] = temp;
}
S -= (max_idx-i); // S>N 일 경우 i는 이미 정렬이 되어있으므로 i를 빼주어야 함
}
for (int i = 0; i < N; i++)
std::cout << A[i] << " ";
std::cout << std::endl;
return 0;
}
헷갈렸던 점
인덱스순서대로 탐색하는 것이 아니다.
교환은 S번 할 수 있다. (이웃한 숫자끼리만 교환 가능)