[BOJ] 1083번_소트_정렬 (C++)

[문제]

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

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 정렬할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 최대 S번까지 할 수 있다. 이 때, 소트한 결과가 내림차순인 것을 출력하는 문제이다.

[사용 알고리즘]

정렬

[풀이 핵심]

• 이 문제는 버블정렬의 개념을 알면 쉽게 해결할 수 있다. 버블정렬이란 서로 인접한 두 원소의 크기를 비교하여 정렬하는 방법이다.
• 버블정렬을 진행하지만, 정렬이 되기 전에 S번 교환이 이루어지면 종료해야한다.
• 버블정렬(내림차순 정렬)은 한단계 진행할 때마다 가장 큰 수의 자리가 고정된다. 그러므로 가장 큰수가 이동한 만큼 S에서 빼주면 교환이 얼마나 진행됐는지 알 수 있다.

[코드]

//boj1083번_소트_정렬

#include<iostream>
#include<vector>

using namespace std;

int main() {
	int N;
	cin >> N;

	vector<int> v;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	int S;
	cin >> S;

	for (int i = 0; i < N - 1; i++) {
		if (S == 0) {
			break;
		}

		int max = v[i];
		int max_index = i;

		for (int j = i+1; j < min(N,i+1+S); j++) {
			if (max < v[j]) {
				max = v[j];
				max_index = j;
			}
		}

		S -= max_index - i;

		for (int k = max_index; k > i; k--) {
			v[k] = v[k - 1];
		}

		v[i] = max;
	}

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

	return 0;
}