[BOJ/C++] 1377 버블 소트

버블 정렬을 수행하며 한번도 일어나지 않은 루프를 찾는 문제입니다.

N이 500,000 이므로 버블 정렬을 이용하면 시간 초과가 발생합니다.

버블 정렬의 안쪽 루프는 특정 데이터가 왼쪽으로 이동할 수 있는 최대 거리가 1이므로

입력 받은 숫자의 정렬 전 인덱스와 정렬 후 인덱스를 비교하면 문제를 해결할 수 있습니다.

1. 정렬 전 인덱스에서 정렬 후 인덱스를 빼면 해당 데이터의 이동 거리가 나오게 됩니다.
2. 가장 움직임이 많은 데이터 즉, 최댓값이 내부 for문의 작동 횟수를 의미합니다.
3. 이후 한번 더 반복문이 실행되는 것을 감안해 1을 더해주면 됩니다.

// boj g2 1377
// 버블 소트

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

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	int count = 0;
	cin >> N;

	vector<pair<int, int>> v(N);

	for (int i = 0; i < N; i++)
	{
		cin >> v[i].first;
		v[i].second = i;
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < N; i++)
	{
		if (v[i].second - i > count)
			count = v[i].second-i;
	}

	cout << count + 1;
	return 0;
}