[백준]Baekjoon1377(정렬)

문제링크 : https://www.acmicpc.net/problem/1377

먼저 이 문제에서 출력하고자하는 i가 무엇인지에 대해 분석을 하면

버블소트를 하면서 정렬이 된 시점을 말한다는 것을 알 수 있다.

즉 버블소트로 1번 돌렸더니 정렬이 다 된다면 i = 1,

2번 돌렸더니 정렬이 다 된다면 i = 2가 되는것이다.

어떻게 하면 버블소트를 돌리지 않고 i를 구할 수 있을까를 알아보기 위해 버블소트가 작동하는

과정을 한번 주목해서 보자

---

문제의 예제대로 한다면

	10	1	5	2	3
i = 1	1	5	2	3	10
i = 2	1	2	3	5	10

이런식으로 최종 정렬이 되는데

우리가 알 수 있는것은 큰 숫자는 한번에 끝까지도 이동할 수 있지만

작은 숫자는 한번 버블소트가 돌 때 한칸씩밖에 움직이지 못한다는 점이다.

고로 처음 배열의 인덱스와 정렬된 배열의 인덱스의 차가 가장 큰 것이 

우리가 원하는 i 값이라는 것을 유추할 수 있다.

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

#define SIZE 5000000

using namespace std;

int main()
{
	long long N; //배열의 크기
	scanf("%lld", &N);
	long long num; //배열에 들어가는 수

	vector<pair<int, int>>v; 
	//pair에서 첫번째 것은 배열에 들어가는 수, 두번째 것은 정렬되기전 index
	for (int i = 0; i < N; i++) {
		scanf("%lld", &num);
		v.push_back(make_pair(num, i)); //숫자와 index 를vector에 삽입
	}
	sort(v.begin(), v.end()); //정렬
	long long max = 0; //차이가 가장 큰 것
	for (int i = 0; i < N; i++) { //i의 값은 정렬된 후 index
		if (v[i].second - i > max) //정렬되기 전 index와 정렬된 후 index의 차를 max와 비교
			max = v[i].second - i;
	}
	printf("%lld\n", max+1); //문제에서는 index가 1부터 시작하기 때문에 1을 더해주면서 보정

}