[C/C++] 백준 #2517 달리기(병합 정렬)

이번 문제는 정렬해서 풀었습니다.  세그먼트 트리를 이용해도 됩니다.  알고리즘 효율은 비슷하겠죠.

 

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

2517번: 달리기

 

정렬은 기본정렬과 고급정렬, 그리고 특수정렬이 있습니다.  특수정렬이 가장 빠르지만, 일반적으로 사용하기 어려운 경우가 많습니다.  기본정렬과 고급정렬은 모두 비교정렬인데, 기본정렬의 시간 복잡도가 \(O(N^2)\)인 데 비해서 고급정렬의 시간 복잡도는 \(O(N \log N)\)입니다.

 

running

 

고급정렬은 퀵정렬, 병합 정렬, 힙 정렬이 있는데, 왜 하필이면 병합 정렬을 사용했는가입니다.  병합 정렬은 다른 고급 정렬과 달리, 입력의 순서를 지키면서 정렬할 수 있습니다.  그래서 병합 정렬을 사용토록 했습니다.

 

그러면 문제를 살펴보면, 달리기를 하는데, 모든 달리기 선수는 능력치가 주어집니다.  그런데, 자신보다 앞에 달리는 선수중에서 능력치가 자기보다 낮으면 남은 거리에 대해서 추월할 가능성이 있습니다.  당연히 뒤에 있는 선수중에 자신보다 능력치가 큰 선수가 있다면 추월당할 수 있지만, 여기서는 얻을 수 있는 최선의 등수를 알아내는 것이기 때문에, 추월당하는 것은 고려하지 않습니다.  결국, 내 앞에 있는 선수들 중에 능력치가 작은 선수들이 몇명이 있는가를 알아내는 것입니다.  예를 들어서 현재 5등을 달리는 선수의 앞에 능력치가 낮은 선수가 3명이 있다면, 이 선수는 2등까지 가능합니다.

 

이를 위해서 입력 순서를 지켜주는 정렬이 필요했고, 이를 통해서 각각의 자리를 정확하게 알 수 있도록 했습니다.

 

//----------------------------------------------------------
//    baekjoon #2517 - Running
//        - by Aubrey Choi
//        - created at 2020-01-23
//----------------------------------------------------------
#include <stdio.h>
#include <memory.h>

int v[500000], idx[500000], n, cnt[500000], t[500000];
void swap(int &a, int &b) { int t=a; a=b; b=t; }
void mergesort(int s, int e)
{
    if(s+1>=e) return;
    if(s+2==e)
    {
        if(v[idx[s]]>v[idx[s+1]]) return;
        cnt[idx[s+1]]++;
        swap(idx[s],idx[s+1]);
        return;
    }
    int c=(s+e)/2, i=s, j=c, k=0;
    mergesort(s,c);
    mergesort(c,e);
    while(i<c && j<e)
    {
        if(v[idx[i]]<v[idx[j]]) {t[k++]=idx[j]; cnt[idx[j]]+=c-i; j++;}
        else t[k++]=idx[i++];
    }
    while(i<c) t[k++]=idx[i++];
    while(j<e) t[k++]=idx[j++];
    memcpy(idx+s,t,k*sizeof(int));
}
int main()
{
    int n, i;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",v+i),idx[i]=i;
    mergesort(0,n);
    for(i=0;i<n;i++) printf("%d\n",i-cnt[i]+1);
}