- 풀이는 간단한 정렬 문제이지만 풀이를 알기까지 오랜 시간이 걸렸다.
- Moo 버블 소트를 1번 진행하면서 원래 자신의 위치보다 오른쪽에 있는 수들은 한칸씩 앞으로 움직이게 된다 . 라서 자신의 위치보다 오른쪽에 있는 수들 중, 가장 자신의 원래 위치보다 먼 수가 버블 소트의 횟수가 될 것이다.
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
int n,num,ans;
vector<pair<int, int>> sorted;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &num);
sorted.push_back({ num,i });
}
sort(sorted.begin(), sorted.end());
for (int i = 0; i < n; i++) {
if (i < sorted[i].second) {
ans = max(ans, sorted[i].second - i);
}
}
cout << ans + 1;
}
