1377 버블소트

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

1377번: 버블 소트

이 문제는 문제에서 주어진 버블 소트 코드를 돌릴 때, 몇 번만에 정렬이 완료되는 지 구하는 문제입니다.

 

풀이 방법 1 :

어떤 숫자보다 크면서, 앞에 위치한 숫자의 개수 중 최대 개수를 이용합니다.

counting inversions 라는 문제와 유사합니다. 단, 다른 점은 counting inversions는 숫자가 한 번씩만 등장하지만,버블 소트는 그렇지 않습니다. counting inversions는 segment tree와 분할정복으로 해결할 수 있는데 이 차이만 유의하면 동일한 방식으로 버블 소트도 해결 할 수 있습니다.

 

 

풀이 방법 2:

정렬하지 않았을 때와 정렬 했을 때의 두 수의 간격을 이용합니다.

ex. 5 4 3 2 1 의 경우

정렬 후는 1 2 3 4 5 입니다.

각각의 인덱스 차이는 4 2 0 2 4 입니다. 

답은 이 중에서 최댓값인 4+1이 됩니다.

 

 

---

<풀이 1 코드> 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;
const ll n_=4e6+100;
ll n,m,k,tc=1,b,c,ans=-1;
ll tree[n_],arr[n_];
vector<pair<ll,ll>> v;

bool compare(pair<ll,ll> a,pair<ll,ll> b){
	if(a.first==b.first) return a.second>b.second; //상대적 순서를 유지하기 위해
	return a.first>b.first;
}
void update(ll N,ll s,ll e,ll idx,ll val){
	if(idx>e||idx<s) return;
	if(s==e){
		if(idx==s) tree[N]++;
		return;
	}
	ll mid=(s+e)/2;
	update(N*2,s,mid,idx,val);
	update(N*2+1,mid+1,e,idx,val);
	tree[N]=tree[N*2]+tree[N*2+1];
}
ll query(ll N,ll s,ll e, ll l, ll r){
	if(l>e || r<s) return 0;
	if(l<=s&&e<=r) return tree[N];
	ll mid=(s+e)/2;
	return query(N*2,s,mid,l,r)+query(N*2+1,mid+1,e,l,r);
}
void solve(){
	cin>>n;
	for(int i=0;i<n;i++) {
        ll a;
		cin>>a;
		v.push_back({a,i});
	}
	sort(v.begin(),v.end(),compare);
	for(int i=0;i<n;i++){
		//cout<<v[i].first<<" "<<v[i].second<<'\n';
		ans=max(ans,query(1,0,n-1,0,v[i].second-1));
		update(1,0,n-1,v[i].second,1);
		
	}
	cout<<ans+1;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	while(tc--) solve();
	return 0;
}

 

 

<풀이 2 코드>

생략..