백준 1377. 버블 소트

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

1377번: 버블 소트

 

이 문제에서 구해야하는건 배열이 주어졌을때 해당 배열이 몇번 만에 버블정렬에 의해 오름차순 정렬되는지를 구해야 한다. 

 

버블 정렬의 원리는 아주 간단한데 배열의 왼쪽에 있는 숫자부터, 오른쪽에 있는 숫자와 비교해 왼쪽이 더 크면 서로 자리를 바꾼다.

바꾼 이후에 또 오른쪽 숫자와 비교해 왼쪽이 더 크면 자리를 바꾼다.

{10, 1, 5, 2, 3}   // 10, 1 비교하면 10 이큼 

{1, 10, 5, 2, 3}  // 10, 5 비교하면 10 이큼 

{1, 5, 10, 2, 3}  

...

이런식으로 거품이 이는 것처럼 큰 숫자가 점점 오른쪽에 위치하게 된다. 

 

버블정렬의 시간 복잡도는 최악 O(N^2)으로 이 문제에서 N은 최대 50만이기 때문에, 뭔가 다른 방법으로 몇번 만에 정렬이 완료되는지 판

단해야 한다. 

 

처음에는 O(N*logN) LIS 크기 판별법으로 접근했는데 이건 아니었다.

 

---

 

버블정렬의 원리를 다시 잘 생각해보면 작은수는 점점 왼쪽에 위치하게 되고, 큰 수는 점점 오른쪽에 위치 하게 된다. 

void BubbleSort() {
    bool changed = false;
    for (int i=1; i<=N+1; i++) {
        changed = false;
        for (int j=1; j<=N-i; j++) {
            if (A[j] > A[j+1]) {
                changed = true;
                swap(A[j], A[j+1]);
            }
        }
        if (!changed) {
            cout << i << '\n';
            break;
        }
    }
}

 

여기서 큰수가 오른쪽으로 가는것은 한번의 i for 문에서 몇번이든 이뤄진다.

하지만 작은수가 왼쪽으로 가는것은 한번의 i for 문에서 단 한번만 이뤄진다.

 

{10, 1, 5, 2, 3}

{1, 5, 2, 3, 10}

{1, 2, 3, 5, 10} 

 

따라서 최초 배열과, 정렬후 배열을 비교해 각 숫자가 왼쪽으로 몇번 이동했는지 판단하고 그 중 가장 큰 값이 답이다.

위에서는 2와3이 왼쪽으로 두번 이동 한것이 최대이므로 2이다.

그런데 최초 상태도 포함해서 계산해야하기 때문에 2 + 1 = 3 이 답이다.