[PS] 백준 1083번 소트(C/C++)

문제

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

입력

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

출력

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

풀이

배열을 정렬할때 연속된 두개의 원소만을 한번만 교환할 수 있다는 생각을 버려야한다.
주어진 S를 통해서 가능한 범위의 최대 값을 찾아서 교환해야 된다.

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

C/C++ 코드

#include<iostream>
#include<vector>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N, S;
	cin >> N;
	vector<int> v(N,0);
	for (int i = 0; i < N; ++i) cin >> v[i];
	cin >> S;
	for (int i = 0; i < N; i++)
	{
		int max = v[i];
		int maxi = i;
		for (int j = i + 1; j < N; j++)
		{
			if (S - (j - i) >= 0)
			{
				if (max < v[j])
				{
					max = v[j];
					maxi = j;
				}
			}
		}
		for (int j = maxi; j > i; j--)
			swap(v[j], v[j - 1]);
		S -= (maxi - i);
		if (S <= 0)
			break;
	}
	for (int i = 0; i < v.size(); i++) cout<<v[i]<<" ";
	return 0;
}

• '사전순으로 가장 뒷서는 것' 이라는 말이 헷갈려 문제가 이해되지 않았다. 내림차순이라고 이해하면될 것 같다.