[백준] 골드2 : (1377) 버블 소트

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

 

이 문제는 버블 정렬을 통해 배열을 정렬할 때, 몇 번 루프만에 정렬이 되었는지를 알아내는 함수이다.

배열 크기가 최대 500,000이기 때문에 절대 제공해 주는 기본 버블 정렬로는 시간 내에 풀 수 없다.

 

버블 정렬의 동작 과정을 생각해보면, 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다.

이는 특정 데이터가 1번의 루프에서 swap으로 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 의미이다.

즉, 데이터의 정렬 전 index와 정렬 후 index를 비교하여 왼쪽으로 가장 많이 이동한 값을 찾으면 그만큼 루프가 수행되었다는 의미이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int N, Answer = 0;
	cin >> N;

	vector<int> Arr1(N);
	vector<pair<int, int>> Arr2(N); // { 수, 기존 인덱스 }
	for (int i = 0, j; i < N; ++i)
	{
		cin >> j;
		Arr1[i] = j;
		Arr2[i] = { j, i };
	}

	// 오름차순 정렬
	sort(Arr2.begin(), Arr2.end());

	for (int i = 0; i < N; ++i)
	{
		if (Arr2[i].second > i)
		{
			// 원점으로부터 이동(정렬 횟수)한 크기만큼 Max 계산
			Answer = max(Answer, Arr2[i].second - i);
		}
	}

	// 이미 정렬이 된 배열이더라도 1번의 루프는 돌기 때문에 +1을 해줌
	cout << Answer + 1 << "\n";
}