[BOJ] 1377 :: 버블 소트

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

백준 풀고 점점 풀이올리기가 귀찮아지는데...

풀이올리면 나도 한번 다시 푸는 방법 복습하는 거니까 다시 열심히 올리려고한다!

우선 이 문제는 우리가 아는 평번한? 버블 소트 문제인데, 

전체 크기인 N의 크기가 너무 커서 실제 버블 소트를 돌리면 TL이 뜬다. 

그래서! 우리는 처음 들어왔을 때 수의 위치와 정렬 후 수의 위치를 비교해 가장 앞으로 많이 옮겨간 수가 몇칸 옮겨갔는지를 찾아주면 되는 문제이다!

이때 정렬할때 algorith 헤더파일에 들어있는 sort함수를 쓰면 nlogn에 정렬이 가능하다.

vector pair로 입력을 받아 first에는 수의 값 second에는 위치를 입력받으면 된다.

후에 first를 기준으로 sort하고 second값과 i번째 값들을 비교해 몇칸 이동했는지를 체크해주면 된다.

#include <iostream>

#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<pair<int, int> > v;
	for (int i = 0; i < n; i++)
	{
		int temp;
		cin >> temp;
		v.push_back(make_pair(temp, i));
	}
	sort(v.begin(), v.end());
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (v[i].second - i > ans)
			ans = v[i].second - i;
	}
	cout << ans + 1 << '\n';
}