백준 1083번 소트

문제

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

입력

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

출력

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

 

버블소트를 그리디 적으로 응용하는 것으로

i번째 좌표에 i+1부터 N까지의 값중 최대 값이 오도록 하는데 그 거리가 남은 카운트 M 이내에 올 수 있는 거리라면

swap해서 오도록 구현하면 된다

 

 

#include<iostream> 
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;

int arr[50];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	int M;
	cin >> M;
	for (int i = 0; i < N; i++)
	{
		int max = arr[i];
		int maxi = i;
		for (int j = i + 1; j < N; j++)
		{
			if (M - (j - i) >= 0)
			{
				if (max < arr[j])
				{
					max = arr[j];
					maxi = j;
				}
			}
		}
		for (int j = maxi; j > i; j--)
			swap(arr[j], arr[j - 1]);
		M -= (maxi - i);
		if (M <= 0)
			break;
	}

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