[백준/C++] 1377번 버블 소트

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

1377번: 버블 소트

당연한 말이지만, 문제에 있는 코드로 풀면 시간초과로 틀린다.

STL에 있는 sort를 활용하는데, 문제의 답은 어떻게 구하냐?

pair를 이용하여 처음 입력받을 때, 숫자와 인덱스를 같이 저장해주면 된다! 

버블 소트는 한번 정렬할 때 마다 제일 큰 수가 맨 뒤로 이동한다. 그렇게 되면 다른 수들은 자연스레 한칸 앞으로 움직이게 되고

버블 소트가 진행되고 난 후 배열의 인덱스와 처음 인덱스를 비교하였을 때, 그 차이가 가장 큰 값이 버블소트의 진행 횟수임을 알 수 있다.

두번째 예시(이미 정렬된 배열)의 답이 1인걸로 보아, 진행 횟수에서 +1을 출력해주면 될 것 같다.

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    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());

    int ans =0;
    for(int i=0; i<n; i++)    {
        if(ans < v[i].second - i)	// 인덱스 차이 비교
            ans = v[i].second - i;
    }
    cout << ans+1;
    return 0;
}