백준 1377번: 버블 소트

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

1377번: 버블 소트

이 문제의 포인트는 버블 소트의 특징을 파악 하는 것이다.

첫번 째로 버블소트는 마지막부터 천천히 채워가는 형식이다.

그리고 뒤에 있던 값이 정렬된 배열의 위치로 가기 위해서는 항상 한칸씩 앞으로 이동하는 것이다.

즉 여기서말하는 몇 단계를 구하기 위해서는 한칸씩 앞으로 가서 본래 위치로 돌아가기 까지의 최대값을 구하면 되는 문제이다.

예를 들어 

10  1 5 2 3 이 주어질때  10이 맨끝으로 가면서 그 앞에 있는 숫자들은 한칸씩 앞으로 간다.

1 5 2 3 10      그리고 5가 끝에서 두번째로 가면서 또 한칸씩 앞으로 간다.

1 2 3 5 10   즉 2,3은 앞으로 두칸씩 이동했고 2번 만에 정렬된것을 확인 할 수 있다.

 

이 코드를 짤 때에 핵심은 위치 값과 최대 값이다. 

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#define PI 3.1415926535
using namespace std;
int d[5000000];
int main()
{	

	
	int n;
	cin >> n;
	vector<pair<int, int>> a(n);            //배열과 위치값을 저장하기 위한 pair
	for (int i = 0; i < n; i++) {
		cin >> a[i].first;                   //배열 값
		a[i].second = i;                     //위치 값
	}
	sort(a.begin(), a.end());
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (ans < a[i].second - i)                     //기존 위치 값에서 바뀐 위치를 뺴준 값
			ans = a[i].second - i;
	}
	cout << ans;
	return 0;
}