버블 소트

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

inversion counting 문제인가? 고민하며 시간을 날렸는데, 결과적으로는 inversion counting 문제가 아니다.

버블 소트의 i에 의해서 돌아가는 한번의 루프를 1회전이라고 불러보자.

각 회전에서 각 원소들은 주변 숫자와의 대소 관계에 따라 오른쪽으로 이동하거나, 왼쪽으로 이동하게된다.

(swap을 한다는 건 사실 누군가는 오른쪽, 누군가는 왼쪽으로 간다는 말이므로 당연한 이야기)

하나의 원소 입장에서 생각해본다면, 그 원소가 1회전에서 왼쪽으로 이동하는 양은 항상 0 또는 1일 수 밖에 없다.

(swap을 당하지 않았거나, 올라오는 중인 버블 수에 의해 swap 당했거나)

모든 수가 정렬된다는 것은 특정 원소가 모두 제자리를 찾아 간다는 말인데, 그렇다면 아래의 명제가 성립한다.

• 모든 수가 정렬되기까지 거치는 회전 수는 각 원소가 정렬되기까지 왼쪽으로 이동한 양 중 최대 값이다.

따라서, 이 문제는 원래 주어진 수열이 정렬되었을 때 왼쪽으로 이동한 양이 가장 큰 녀석을 찾는 문제로 볼 수 있다.

이때, 수열에 같은 값이 있을 수 있고 주어진 코드가 클 때만 swap을 진행하므로 정렬에만 stable_sort를 써주면 된다.

#include <iostream>
#include <utility>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

size_t Solve(vector<pair<size_t, size_t> >& arr)
{
  stable_sort(arr.begin(), arr.end());

  size_t max_move = 0;

  for (size_t idx = 0; idx < arr.size(); ++idx)
  {
    if (arr[idx].second > idx)
    {
      max_move = max(max_move, arr[idx].second - idx);
    }
  }

  return max_move + 1;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  size_t N;

  cin >> N;
  vector<pair<size_t, size_t> > ARR(N);

  for (size_t it = 0; it < N; ++it)
  {
    cin >> ARR[it].first;
    ARR[it].second = it;
  }

  // Solve
  cout << Solve(ARR) << '\n';

  return 0;
}