[1377] 버블 소트 (C++)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n; cin >> n;
	vector<pair<int, int>> A(n);
	vector<int> result(n);

	for (int i = 0; i < n; i++) {
		cin >> A[i].first;
		A[i].second = i;
	}

	sort(A.begin(), A.end());

	for (int i = 0; i < n; i++) {
		result[i] = A[i].second - i;
	}

	sort(result.begin(), result.end());

	cout << result[n - 1] + 1 << endl;

	return 0;
}

 

1. 해당 문제에서 구하려는 것은 '몇 번째 수행에서 버블 정렬이 완료되는가'

2. 큰 수는 한 번의 버블 정렬 중 여러번 이동 할 수 있지만, 작은 수는 한 번의 버블 정렬 중 한번만 이동한다

=> 좌측으로 이동한 값 중 '가장 많이 이동한 횟수+1'를 구하는 것(원본도 포함해야 하므로 +1)

3. pair vector를 사용해 first에는 값, second에는 index를 정리

4. 정렬이 완료된 vector A의 second(index)값에 +1을 한 값을 result라는 vector에 정리

5. result를 sort하고 가장 큰 값(result[n-1] 항)에 +1 한 값을 출력