[백준] 1377번 : 버블 소트 C++ 문제풀이 솔루션

문제

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

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 == false) {
        cout << i << '\n';
        break;
    }
}

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

정답을 출력한다.

 

 

버블 정렬의 이중 for 문에서 정렬될 때 까지의 바깥쪽 for문 실행 횟수를 구해야한다. 

N의 최대 범위가 500,000이므로 시간복잡도가 O(n^2)인 버블 정렬을 사용하면 시간이 초과된다.

버블 정렬에서 원소가 왼쪽으로 이동하는 것은 루프 당 한 번이므로

정렬 전의 인덱스와 정렬 후의 인덱스를 비교하여 왼쪽으로 이동한 횟수의 최댓값을 구한다.

#include <iostream>
#include <vector>
#include <algorithm>

#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false)
using namespace std;

int main() {
  fast_io;
  int n;
  cin >> n;
  int result = 0;
  vector<pair<int, int>> bub(n);
  for (int i = 0; i < n; i++) {
    cin >> bub[i].first;
    bub[i].second = i;
  }
  sort(bub.begin(), bub.end());
  for (int i = 0; i < n; i++) {
    if (bub[i].second - i > result) result = bub[i].second - i;
  }
  cout << result + 1;
  return 0;
}