[BOJ. 1377] 버블 소트

1. 링크 백준 1377

2. 풀이

이 문제는 무작정 코드에 있는 버블 소트를 복사 붙여넣기를 한다면 시간초과가 일어난다.

그러면 $O(N^2)$이 아닌 다른 방법을 찾아야 한다.

bool change = false;
for (int i=1; i<=n+1; i++) {
    change = false;
    for (int j=1; j<=n-i; j++) {
        if (a[j] > a[j+1]) {
            change = true;
            swap(a[j], a[j+1]);
        }
    }
    if (change == false) {
        cout << i << '\n';
        break;
    }
}

위와 같은 버블 소트를 직접하면 다음과 같은 일이 발생한다.

10 1 5 2 3

10 1 5 2 3
1 10 5 2 3
1 5 10 2 3
1 5 2 10 3
1 5 2 3 10

1 5 2 3 10
1 2 5 3 10
1 2 3 5 10

여기서 우리가 알 수 있는 것은 버블 소트 사이클마다 다른 수들이 한 칸씩 앞으로 이동한다는 것을 알 수 있다.

그리고 끝까지 이동하는 숫자가 얼마만큼 움직였는 지를 보면 사이클이 몇 번 일어났는 지 알 수 있다.

그러므로 우리는 (정렬하기 전의 위치 - 정렬한 후의 위치)의 최대값을 찾으면 된다.

3. 코드

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

using namespace std;

pair<int, int> arr[500000];

int main(void)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].first;
        arr[i].second = i;
    }
    sort(arr, arr + n);

    int maximumMove = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i].second - i > maximumMove)
            maximumMove = arr[i].second - i;
    }
    cout << maximumMove  + 1 << '\n';
}