[백준/BOJ] 백준 1377번 : 버블 소트

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

1377번: 버블 소트

 

버블 소트가 언제 끝나는지 외부 반복의 횟수를 확인하는 문제이다.

우선 버블 소트는 내부 반복문이 수행될 때마다 앞, 뒤 숫자를 비교 후 앞에 있는 숫자가 바로 뒤 숫자보다 크면 자리를 바꾸는데, 자리를 바꾸며 앞으로 옮겨지는것은 내부 반복문 한번 수행에 대해 각 숫자당 최대 한 번이다. 즉, 한 번의 내부반복에서 앞으로 옮겨진 것은 또 앞으로 옮겨지지 않는다. 또한 자신보다 더 큰 숫자가 이미 뒤로 한칸 이동했으므로 한번 앞으로 옮겨진 숫자는 다시 더 뒤로 가지 않는다.

이러한 특성을 이용해 정렬 후, 가장 앞으로 옮겨진 숫자가 얼만큼 앞으로 이동했는지를 통해 정렬이 끝나는 외부 반복 횟수를 구할 수 있다.

 

코드

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

int n;

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

	cin >> n;

	//언제 정렬이 끝나는지 외부 반복의 횟수를 확인하는 방법으로 문제를 해결
	//버블정렬은 내부 반복문이 수행될때 마다 앞,뒤 숫자를 비교 후 앞에 있는 숫자가 바로 뒤 숫자보다 크면 자리를 바꾼다
	//이때, 자리를 바꾸는것을 통해 앞으로 옮겨지는것은 내부 반복문 한번 수행에 대해 각 숫자당 최대 한번이다 (한번의 내부반복에서 앞으로 옮겨진것은 또 앞으로 옮겨지지 않는다)
	//또한 한번 앞으로 옮겨진 숫자는 다시 더 뒤로 가지 않는다 (자신보다 더 큰 숫자가 이미 뒤로 한칸 이동했으므로)
	//즉 최대 앞으로 옮겨진 숫자의 횟수를 통해 정렬이 끝나는 외부 반복 횟수를 구할 수 있다.

	vector<pair<int, int>> check;
	for (int i = 0; i < n; i++) {
		int number;
		cin >> number;

		//버블 소트는 안정정렬이므로 같은 숫자의 경우를 대비해, 처음 위치도 함께 저장
		check.push_back(make_pair(number, i));
	}

	//오름차순 정렬, 같은 숫자일 경우 먼저 들어온 숫자가 앞에 위치하도록 해서 안정정렬
	sort(check.begin(), check.end());

	int max_front_move = -1;
	for (int i = 0; i < check.size(); i++) {
		int before_index = check[i].second;
		int after_index = i;

		max_front_move = max(max_front_move, before_index - after_index);
	}

	//changed가 false일 경우 수행 되는 외부 반복을 고려해서 +1 수행
	int result = max_front_move + 1;

	cout << result;

	return 0;
}