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

using namespace std;
typedef struct _arr
{
    int val;
    int idx;
    int after;
} Arr;
vector<Arr> A;
bool cmp(Arr &a1, Arr &a2)
{
    if (a1.val != a2.val)
    {
        return a1.val < a2.val;
    }
    else
        return a1.idx < a2.idx;
}
int main(void)
{

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        int value;

        cin >> value;
        A.push_back({value, i - 1, 0});
    }

    sort(A.begin(), A.end(), cmp);
    for (int i = 0; i < A.size(); i++)
    {
        A[i].after = i;
    }
    int maxidx = 0;
    for (int i = 0; i < A.size(); i++)
    {
        if (A[i].idx - A[i].after > maxidx)
            maxidx = A[i].idx - A[i].after;
    }
    cout << maxidx + 1;
    return 0;
}

문제 접근

버블 소트가 몇 번째 횟수 만에 완성되는지 찾는 것인데, 문제에 있는 코드로는 버블 소트의 시간 복잡도가 O(N^2) 이므로 시간 초과가 난다.

해결 방법

sort 를 O(nlogn) 만에 하고 인덱스 차이를 통해 비교한다. 즉, 뒤에 있던 숫자가 앞에 어느정도 까지 앞당겨 졌는지 인덱스 최대 차이를 구하므로써 시간복잡도 O(nlogn)만에 해결 가능하다.

의문점 및 헷갈린 점

인덱스 차이 뿐만 아니라 stable sort 또한 고려해야 한다. stable sort 란 값이 똑같으면 처음 상태를 유지하는 것인데 즉 11111 값이 들어왔을때 나중인덱스가 동일한 11111이어도 05124 번째 순서로 들어오면 안된다는 뜻이다. 따라서 나는 cmp 정렬 방식에 값이 같을 경우 처음 idx 순서로 정렬하게 하였다.