문제

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

풀이

문제의 핵심적인 조건은 다음과 같다.

• 배열의 크기 N <= 50
• 연속된 두개의 원소만 교환 가능
• 교환은 S번 이하 (S <= 10^6)
• 정렬 결과, 사전순으로 가장 뒤쪽에 오는 배열 출력

교환은 최대 S번까지 할 수 있으므로, 연속된 두 원소의 순서를 교환하는 모든 경우의 수는

1 + 2 + ... + S = S * (S+1) / 2 이다.

그런데, S는 최대 100만이므로 위와 같이 모든 경우의 수를 구하고 그 중에서 사전순으로 가장 뒤쪽에 오는 배열을 출력하는, 브루트포스 방법으로는 시간초과가 날 수밖에 없다.

사전순으로 가장 뒤쪽에 있는 배열을 구하려면, 크기가 큰 원소일수록 배열의 앞부분에 위치해야 한다. 즉, 그리디하게 가장 큰 숫자를 최대한 앞으로 당겨와야 한다는 의미이다.

가장 큰 숫자를 앞으로 당겨오고 그 중간에 있던 원소들은 한칸씩 뒤로 보내면서 발생한 swap 횟수를 S에서 차감해준다.

#include <iostream>
#include <string> 
#include <algorithm>
#include <vector> 
#include <set>
using namespace std;

const int MAX = 51; 
int arr[MAX]; 
int N, S;

void input() {
	cin >> N; 

	for(int i = 0; i < N; i++){
		cin >> arr[i];
	}

	cin >> S; 
}

void solution() {
	int start = 0;

	// S번 이하의 스왑으로 
	// 최댓값을 start 위치로 끌어오기
	while(start < N && S > 0) {
		int maxIdx = start; 

		// [start, start + S] 범위의 원소들 중에서 
		// 최댓값의 인덱스 저장 
		for(int i = start; i <= min(N - 1, start + S); i++){
			if(arr[maxIdx] < arr[i]) maxIdx = i; 
		}

		// 최댓값을 start 위치로 한칸씩 앞당기면서 S값 차감 
		for(int i = maxIdx; i > start; i--){
			swap(arr[i], arr[i - 1]);
			S--; 
		}

		start++;
	}

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	input(); 

	solution(); 

	return 0;
}