[BOJ]1377번: 버블 소트 (c++)

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

1377번: 버블 소트

 

정렬, O(N)

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

using namespace std;

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

	// 입력
	int N;
	cin >> N;
	vector<pair<int, int>> v(N);
	for (int i = 0; i < N; ++i)
	{
		// 입력된 순서 저장
		v[i].second = i;
		cin >> v[i].first;
	}

	// 정렬
	sort(v.begin(), v.end());

	// 입력된 순서와 정렬된 순서 비교
	int max_moved = 0;
	for (int i = 0; i < N; ++i)
	{
		// 뒤에서 앞으로 이동한 최대 칸수 구하기
		if (max_moved < v[i].second - i)
		{
			max_moved = v[i].second - i;
		}
	}

	// 최대로 이동한 횟수 + 1 : 몇회만에 버블정렬이 되었는지
	cout << max_moved + 1;

	return 0;
}

 

영식이는 다음과 같은 버블 소트 프로그램을 C++로 작성했다.

(생략)

위 소스에서 n은 배열의 크기이고, a는 수가 들어있는 배열이다. 수는 배열의 1번방부터 채운다.
위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구하는 프로그램을 작성하시오.

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다.

 

버블소트와 관련된 코드를 주고, 그와 동일한 값을 출력하도록 하는 문제이다.

처음엔 주어진 코드를 그대로 출력시키라는 말인줄 알았는데, 

배열의 크기가 500000이므로

이중포문 버블소트를 그대로 갖다 쓰면 O(N^2) (=250,000,000,000)의 시간 복잡도가...

 

따라서 주어진 코드의 결과값인 "정렬이 되기까지 버블소트를 진행하는 횟수"를 

다른 코드로 작성해야 한다.

 

 

버블정렬을 참고한 블로그

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

버블정렬은 앞의 요소보다 작은 뒤의 요소를 한칸씩 앞으로 당겨오는 정렬이므로

1회에는 요소들이 최대 1칸씩 이동하게 된다.

 

따라서 최종 정렬된 숫자열과 비교해서 어떤 요소가 최대 K칸을 이동했다면

버블정렬은 K + 1회차에 완성된 것이다. 

 

 

처음엔 벡터를 2개 만들어서 원본/정렬된 후의 벡터의 인덱스를 비교했었는데

O(N^2)의 코드에서 가지를 쳐서 간신히 AC를 받았다ㅋㅋ

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

using namespace std;

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

	// 입력
	int N;
	cin >> N;
	vector<int> a(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> a[i];
	}

	// 숫자열 복사
	vector<int> v(a);

	// 복사된 숫자열 정렬
	sort(v.begin(), v.end());

	// 원본 숫자열을 탐색하여 정렬된 숫자열과 비교
	int max_moved = 0;
	for (int i = N - 1; i >= 0; --i)
	{
		// 뒤에 있던 숫자가 앞으로 온 경우
		if (a[i] < v[i])
		{
			// 정렬된 벡터에서 해당 숫자 찾기
			for (int j = i - 1; j >= 0; --j)
			{
				if (a[i] == v[j])
				{
					// 최대 위치 차이값 갱신
					max_moved = max(i - j, max_moved);
					break;
				}
			}
		}
	}

	// 최대로 이동한 횟수 + 1 : 몇회만에 버블정렬이 되었는지
	cout << max_moved + 1 << '\n';

	return 0;
}

 

그보다 처음부터 입력된 순서를 pair로 저장한 후 정렬해서

정렬된 인덱스와 pair.second값을 비교하는 것이 O(N)으로 깔끔하게 끝난다. 

// 입력된 순서와 정렬된 순서 비교
int max_moved = 0;
for (int i = 0; i < N; ++i)
{
	// 뒤에서 앞으로 이동한 최대 칸수 구하기
	if (max_moved < v[i].second - i)
	{
		max_moved = v[i].second - i;
	}
}