[백준] 1377 버블 소트 - C++

문제) 버블 소트의 모든 데이터가 정렬 되었을 때, i 값을 출력하도록 한 소스를 C++로 작성해보았다. 해당 코드를 실행했을 때의 결과값을 출력하는 프로그램을 만들어보자.

    입력으로 500,000보다 작거나 같은 n이 주어지고, 둘째줄 부터 n번째 줄까지 배열의 수가 주어진다.

    시간제한은 2초, 메모리 제한은 128MB이다.

 

문제는 버블소트지만 n이 500000까지이기 때문에 진짜 버블소트로 풀면 시간 초과가 난다. nlogn으로 정렬을 우선 한 후 데이터의 정렬 전 인덱스와 정렬 후 인덱스의 최대값을 찾으면 i값을 구할 수 있다.

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

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<pair<int, int>> a(n);

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

	sort(a.begin(), a.end());
	int max = 0;

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

	cout << max + 1;


	return 0;
}