[BOJ] 2517 : 달리기

2517 : 달리기

풀이

mergesort

처음 순위를 1부터 쭈욱 기록해둔 다음에,

머지소트 하는 도중 뒷순위의 친구들이 앞친구들을 앞지르면서 merge될때,

앞지른 만큼씩 base배열의 값을 빼주면서 머지소트를 진행하면 된다.

숫자가 10억까지 가능하므로, 처음에 주어진 순위가 머지소트가 되면서 함께 변경이 되도록 arr를 만들었고,

앞지른 만큼씩 base배열에 빼줄때 base[arr[j]]로 접근해서 빼주도록 했다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
#include <map>
using namespace std;
//머지되면서 인덱스위치를 변경시켜 기록
int arr[500001];
int arr2[500001];
//출력할 배열
int base[500001];
//데이터
int s[500001];
//머지용 임시데이터
int v[500001];

void merge(int m, int middle, int n) {
    int i = m;
    int j = middle + 1;
    int k = m;
    while (i <= middle && j <= n) {
        if (s[i] > s[j]) {
            v[k] = s[i];
            arr2[k] = arr[i];
            i++;
        }
        else {
            v[k] = s[j];
            arr2[k] = arr[j];
            base[arr[j]] -= (middle + 1 - i);
            j++;
        }
        k++;
    }
    if (i>middle) {
        for (int t = j; t <= n; t++) {
            v[k] = s[t];
            arr2[k] = arr[t];
            k++;
        }
    }
    else {
        for (int t = i; t <= middle; t++) {
            v[k] = s[t];
            arr2[k] = arr[t];
            k++;
        }
    }
    for (int t = m; t <= n; t++) {
        s[t] = v[t];
        arr[t] = arr2[t];
    }
}

void mergeSort(int m, int n) {
    if (m < n) {
        int middle = (m + n) / 2;
        mergeSort(m, middle);
        mergeSort(middle + 1, n);
        merge(m, middle, n);
    }
}


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

    int n;
    cin >> n;
    for (int i = 0; i<n; i++) {
        int tmp;
        cin >> tmp;
        arr[i] = i;
        base[i] = i + 1;
        s[i] = tmp;
    }
    mergeSort(0, n - 1);
    for (int i = 0; i<n; i++) {
        cout << base[i] << '\n';
    }
    return 0;
}

Written on July 17, 2019