[백준 골드2] 1377 버블 소트

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

 

swap된 거리가 가장 길었던 것에 +1을 하면 된다.

여기서 버블 정렬의 이중 for문에서 안쪽 for문이 돌 때

swap이 일어나지 않은 반복문이 한 번 더 실행되는 것을 감안해 최댓값에 1을 더한다.

 

 

#include <string>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iostream>

using namespace std;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, max = 0;

    cin >> n;
    vector<pair<int, int>>v(n);

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

    sort(v.begin(), v.end());
    
    for (int i = 0; i < n; i++) {
        if (max < v[i].second - i) {
            max = v[i].second - i;
        }
    }

    cout << max + 1;

    return 0;
}