BOJ 1517 버블 소트

 

문제 링크 : https://www.acmicpc.net/problem/1517

1517번: 버블 소트

 

입력된 순서 index 와 값을 정렬했을 때 순서가 엇갈린 개수를 찾는 문제이다.

문제의 기술에서는 인접한 두 수만을 비교하지만 멀리 떨어져 있어도 언젠가는 비교해서 swap 된다.

 

우선 문제의 카테고리는 세그먼트 트리이지만 다른 풀이부터 보자.

 

1. Merge Sort

가장 직관적인 해법은 실제 버블 소트를 구현해서 swap 개수를 구하는 것이다.

그러나 $O(n^2)$ 시간이 필요하니 이렇게는 곤란하다.

앞서 얘기했지만 멀리 떨어진 두 항도 정렬되기 위해서는 언젠가는 비교되고 swap 개수에 더해짐을 이용하자.

즉, 아무 정렬 알고리즘에서도 swap 개수를 구하는 것이 가능하다는 것이다.

 

그래서 merge sort 를 수행하면서 크기가 역전되어 있는 것을 찾으면 된다.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int arr[500001], tmp[500001];

ll merge(int s, int mid, int e){
    int l=s, r=mid+1, p=s;
    ll ans=0;
    while(l<=mid && r<=e){
        if(arr[l]<=arr[r]) {
            tmp[p++]=arr[l++];
        } else {
            ans+=(mid-l+1);
            tmp[p++]=arr[r++];
        }
    }
    
    if(l==mid+1) while(r<=e) tmp[p++]=arr[r++];
    else while(l<=mid) tmp[p++]=arr[l++];
    for(int i=s;i<=e;i++) arr[i]=tmp[i];
    return ans;
}

ll msort(int l,int r){
    if(l==r) return 0;
    
    ll ans=0;
    int mid=l+r>>1;
    ans+=msort(l,mid), ans+=msort(mid+1,r);
    ans+=merge(l,mid,r);
    return ans;
}

int main(){
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    
    printf("%lld\n", msort(1,n));
}

 

문제를 분할해서 해결하고 있다.

merge 함수 내에서 왼쪽 절반과 오른쪽 절반 사이의 크기 역전 개수를 찾는 방법만 이해하면 된다.

 

2. Segment Tree

value 와 index 를 묶어서 value 크기 역순으로 정렬한다.(크기 순으로 정렬해도 되지만 마지막 계산이 번거롭다.)

그리고 하나씩 꺼내 index 위치에 1 을 segment tree 에 업데이트하고 구간합을 구하면 된다.

(입력되는 값의 크기가 커서 index 를 tree 로 다룬다. 좌표 압축을 해서 값을 tree 에 저장해도 된다.)

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pii=pair<int,int>;

int n,tree[1500000];
pii arr[500000];

void upd(int l,int r,int node,int p,int v){
    if(p<l || r<p) return;
    if(l==r) {tree[node]+=v; return;}
    int mid=l+r>>1;
    upd(l,mid,2*node,p,v), upd(mid+1,r,2*node+1,p,v);
    tree[node]=tree[2*node]+tree[2*node+1];
}

int qry(int l,int r,int node,int ql,int qr){
    if(qr<l || r<ql) return 0;
    if(ql<=l && r<=qr) return tree[node];
    int mid=l+r>>1;
    return qry(l,mid,2*node,ql,qr)+qry(mid+1,r,2*node+1,ql,qr);
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        int t; scanf("%d",&t);
        arr[i]={t,i};
    }
    
    sort(arr,arr+n,[&](pii &a, pii&b){
        if(a.first==b.first) return a.second>b.second;
        return a.first>b.first;
    });
    
    ll ans=0;
    for(int i=0;i<n;i++){
        int c=qry(0,n-1, 1, 0,arr[i].second);
        ans+=c;
        upd(0,n-1,1, arr[i].second, 1);
    }
    
    printf("%lld\n", ans);
}

 

논리적으로는 문제 없지만 tree 단말의 값은 기껏해야 1 인데 세그먼트 트리는 사치다.

 

3. Fenwick Tree

비효율적으로 코딩되었지만 귀찮아서 그냥 올린다.

중요한 것은 하나씩 update 하면서 부분합을 구하는 과정에서 어떻게 크기가 역전된 쌍의 개수를 찾는지 이해하는 것이다.

 

//#include<bits/stdc++.h>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int sz=1;
int arr[500001], ss[500001];
vector<pair<int,int>> cpy;

void upd(int p, int v) {
    for(;p<=sz;p+=p&-p)
        ss[p]+=v;
}

int qry(int p) {
    int ans=0;
    for(;p>0;p&=p-1)
        ans+=ss[p];
    return ans;
}

int main() {
    int n; scanf("%d",&n);
    sz=n;

    cpy=vector<pair<int,int>>(n+1,{0,0});
    
    for(int i=0;i<n;i++) {
        scanf("%d", arr+i);
        cpy[i]={arr[i],i};
    }
    
    sort(cpy.begin(), cpy.begin()+n);
    int cnt=0; 
    int prv=cpy[0].first;
    arr[cpy[0].second]=cnt+1;
    for(int i=1;i<n;i++) {
        if(prv==cpy[i].first) {
            arr[cpy[i].second]=cnt+1;
        } else {
            cnt++;
            arr[cpy[i].second]=cnt+1;
            prv=cpy[i].first;
        }
    }

    long long ans=0;
    for(int i=0;i<n;i++) {
        int t=qry(arr[i]);
        ans+=i-t;
        upd(arr[i],1);
    }

    printf("%lld\n", ans);
}