백준 1377(버블 소트) c++

문제

1377번: 버블 소트

간단히 버블소트가 몇단계 만에 완성되는지 출력하는 문제입니다.

버블 소트는 한단계 실행 할때마다 배열안의 가장큰수가 맨뒤로 갑니다.

하지만 단순히 문제안에 있는 코드를 배껴서 제출하면 시간초과가 납니다.

버블소트의 시간복잡도는 O(N^2)인데 N이 최대 500만 까지 가능하므로 

500만 * 500만 이면 시간이 너무 많이 듭니다.

굳이 정렬을 진행하지 않고 몇단계 만에 정렬이 되는지를 구하는것이 관건입니다.

코드를 보겠습니다.

int n;
cin >> n;
vector<pair<int, int>>v(n);
for (int i = 0; i < n; i++) {
	cin >> v[i].first;
	v[i].second = i;
}
sort(v.begin(), v.end());
int key = 0;

for (int i = 0; i < n; i++) {
	key = max(v[i].second - i, key);
}
cout << key + 1;

배열의 크기인 n을 입력받고, 배열의 값과 그 값의 인덱스 번호를 pair형태로 받아 주었습니다.

그 다음 pair형태로 받은 배열을 정렬해줍니다. 여기서 정렬의 시간복잡도는 O(N log N)이므로 시간에는 크게 상관없습니다.

여기서 중요한것이 처음에 받았던 배열의 인덱스 값을 정렬하고 난이후에 인덱스 값으로 빼줍니다.

버블소트는 한단계씩 실행할때마다 swap하므로 인덱스값이 한칸씩 이동합니다. 

그러므로 이동한 수가 가장큰수가 그 배열이 단계적으로 버블소트를 진행한 단계와 같습니다.

따라서 처음에 인덱스 번호에서 정렬한 이후 인덱스 번호를 빼준 값중 가장 큰수.  즉, 원소의 이동이 가장 큰 값이

버블소트의 단계입니다.

그 값을 변수 key에 저장해줍니다.

마지막에 key값에 +1을 하였는데 문제에서는 인덱스 처음값을 1로 잡았지만 우리는 인덱스 번호를 0으로 잡았기 때문에 1을 더해줍니다.

---

전체 코드입니다.

#include<iostream>
#include<vector>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	vector<pair<int, int>>v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i].first;
		v[i].second = i;
	}
	sort(v.begin(), v.end());
	int key = 0;

	for (int i = 0; i < n; i++) {
		key = max(v[i].second - i, key);
	}
	cout << key + 1;

	
	
	return 0;
}