(9) [C++] 백준 No.1377 : 버블 소트

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터5-5-정렬-문제풀이2-1

 

# C++

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    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()); // NlogN의 시간복잡도

    int ans = 0;

    for (int i = 0; i < n; i++){
        if (ans < (v[i].second - i)){
            ans = v[i].second - i;
        }
    }

    cout << ans + 1 << "\n";
}