[C++] 버블버블 (백준 31870번)

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

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int ans = 1000000000;
    for (int k = 0; k < n; k++) {
        vector<int> at = a;
        int cnt = 0;
        for (int i = n - 1; i > 0; i--) {
            if (i == k) {
                reverse(at.begin(), at.end());
                cnt++;
            }
            for (int j = 0; j < i; j++) {
                if (at[j] > at[j + 1]) {
                    int tmp = at[j];
                    at[j] = at[j + 1];
                    at[j + 1] = tmp;
                    cnt++;
                }
            }
        }
        ans = min(ans, cnt);
    }

    cout << ans << '\n';
}

[첫번째 풀이]

무려 n^3의 시간복잡도를 가지는 코드이다.

그냥 단순무식하게 버블 정렬 n^2에다가 어느 시점에서 전체 반전을 시킬지 n으로 해서 n^3으로 푼 것이다. n이 1000이라서 되려나? 안 되려나? 했는데 이게 되네. 704ms로 겨우 통과 (AC)

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // ascending order
    vector<int> at = a;
    int asccnt = 0;
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (at[j] > at[j + 1]) {
                int tmp = at[j];
                at[j] = at[j + 1];
                at[j + 1] = tmp;
                asccnt++;
            }
        }
    }

    // descending order
    at = a;
    int descnt = 0;
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (at[j] < at[j + 1]) {
                int tmp = at[j];
                at[j] = at[j + 1];
                at[j + 1] = tmp;
                descnt++;
            }
        }
    }

    cout << min(asccnt, descnt + 1) << '\n';
}

[두번째 풀이]

아마도 이게 정해일 듯하다. 

(오름차순 정렬할 때 횟수)와 (내림차순 정렬할 때 횟수 + 1)을 비교하면 된다. 즉, 반전시키지 않은 경우와 맨 처음에 반전시킨 경우를 비교하는 것이다. 

이 두 가지 경우만 비교해도 되는 이유는, 중간에 반전시킨다는 것은 이전까지 버블 정렬로 하던 행동들이 전부 결과의 반대 방향으로 이끄는 행동이어서 무조건 횟수가 늘어나기 때문이다. 

(AC)