<백준> 1377

버블 소트

문제

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

출력
정답을 출력한다.

버블 정렬을 실제로 수행하는 것이 아닌, 버블 정렬이 몇 번의 패스를 수행해야 정렬이 완료되는지를 구하는 문제이다.

이동 거리 = 원래 인덱스 - 정렬 후 인덱스
정답 = 이동거리 + 1이다.

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	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());

	int max = 0;

	for (int i = 0; i < n; i++)
	{
		if (v[i].second - i > max)
		{
			max = v[i].second - i;
		}
	}
	cout << max + 1;
}