[Baekjoon 1377 | C++] Bubble Sort

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

처음에 준 예제로 문제 풀었다가 시간 초과가 발생했다. 그래서 정렬되기 전과 후를 비교해서 각 값들이 얼만큼 이동했는 지 계산해보고 최대값만 선별하여 문제를 해결했다.

이거는 좋은 문제인 것 같아서 시험 끝나고 풀이를 다시 작성해볼 예정이다.

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using pii = pair<int, int>;
using vpii = vector<pii>;

#define MAX 1000001

int N;
vpii A;

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

    cin >> N;

    int x;
    for (int i = 1; i <= N; ++i) {
        cin >> x;
        A.push_back({x, i});
    }

    sort(A.begin(), A.end());

    int result = 0;
    for (int i = 0; i < A.size(); ++i) {
        result = max(result, A[i].second - i);
    }
    cout << result;

    return 0;
}