190203 BOJ 2517번 달리기

머지 소트를 이용한 문제 풀이

풀이 설명을 들었을 땐 이해가 갔지만 정작 머지 소트를 구현하지 못해 시간을 많이 소모했다. ㅜㅜ

53번째 줄처럼 정렬한 배열을 원래 배열에 업데이트를 해줘야 하는데 안해서 혼란에 빠졌다....

풀이의 핵심은 머지 소트 과정에서 배열을 두 조각으로 나눴을 때 각각 맨 앞에 있는 원소끼리 대소 비교를 한다.

이 때 오른쪽 수가 더 크다면 임시 배열에 넣고 왼쪽에 남아있는 숫자들의 갯수 만큼 순위를 빼주면 된다.

자신보다 앞에 있는 선수만 보면 되기 때문이다.

세그먼트 트리로 풀 수도 있다고 하는데 감이 안온다....

#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
#include <functional>
#include <string>
#include <deque>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define endl '\n'
#define ll long long
#define un unsigned
#define mp(a,b) make_pair(a,b)
#define sws ios::sync_with_stdio(false), cin.tie(NULL)
#define MAX_INT 2147000000
#define pii pair<int, int>
using namespace std;
 
class info {
public:
    int first, second, init;
};
info A[500002];
info tmp[500002];
int N;
bool cmp(info a, info b) {
    return a.init < b.init;
}
void msort(int st, int ed) {
    if (st == ed) return;
    else if (ed - st == 1) {
        if (A[ed].first > A[st].first) {
            A[ed].second--;
            swap(A[st], A[ed]);
        }
    }
    else {
        int left = st;
        int mid = (st + ed) / 2;
        int right = mid + 1;
        msort(left, mid);
        msort(right, ed);
        for(int i = st; i <= ed; i++) {
            if (left > mid) tmp[i] = A[right++];
            else if (right > ed) tmp[i] = A[left++];
            else if (A[left].first < A[right].first) {
                tmp[i] = A[right++];
                tmp[i].second -= (mid - left + 1);
            }
            else     tmp[i] = A[left++];
        }
        for(int i = st; i <= ed; i++) A[i] = tmp[i];
    }
}
 
int main() {
    sws;
    cin >> N;
    FOR(i, 0, N) {
        cin >> A[i].first;
        A[i].second = i;
        A[i].init = i;
    }
    msort(0, N - 1);
    sort(A, A + N, cmp);
    FOR(i, 0, N) cout << A[i].second + 1 << endl;
}