[BOJ 1377] 버블 소트

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

버블 소트가 총 몇 회 발생하는지 찾는 문제이다. 

하지만 그냥 실제로 버블 소트를 하면서 버블 소트 횟수를 찾게되면 N의 제한이 50만이고 복잡도가 O(N^2)이므로 시간초과이다. 

이 문제의 경우 버블 소트의 특성을 잘 이해하면 풀 수 있는 문제이다. 

버블 소트의 경우 한번 반복될 때 오른쪽으로는 몇번을 이동하게 되던, 왼쪽으로는 어떤 수이던 딱 한번만 움직이게 된다. 

따라서 처음 입력에서 sort한 이후에 인덱스의 차이가 가장 큰 경우를 찾아주면 되는 문제이다. 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <stdio.h>
#define INF 1e9
typedef long long ll;
 
using namespace std;
int n;
vector<pair<int,int>> v;
 
int main(){
    cin >>n;
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        v.push_back({a,i});
    }
    sort(v.begin(),v.end());
    
    int ans= 0;
    for(int i=0;i<n;i++){
        if(ans < v[i].second-i){
            ans = v[i].second-i;
        }
    }
    cout <<ans+1 <<endl;
}