BOJ : 2517 달리기

---

[BOJ 2517(P4)리뷰]

이 문제는 Inversion Count 알고리즘을 이용하여 해결할 수 있다.

문제를 잘 읽어보자. 각각의 선수들은 달리기를 하고 있는데, 자신보다 앞에 있는 선수보다 실력이 좋으면 그 선수를 따라잡을 수 있다고 한다. 이 때 각각의 선수들의 최선의 등수를 구해야 한다.

즉, 문제를 쉽게 풀자면 각각의 선수마다 자신의 앞에있는 선수 중 자신보다 능력치가 낮은 선수가 몇명인지 구하여 자신이 그 선수들을 따라잡았을 때의 최종등수가 몇등이냐를 구해야 하는 문제이다.

가장 쉬운 풀이로는 각각의 선수마다 앞의 있는 선수들을 탐색하는 O(N^2)풀이를 떠올리겠지만 이 풀이로는 시간초과를 맞게된다. 더 효율적인 알고리즘이 필요하다.

이 때 사용한 방법이 inversion count다. 머지소트를 이용하여 각 배열의 원소마다 자신의 앞에 있는 숫자 중 자신보다 작은 숫자들의 갯수를 기록하여 자신의 현재 위치 - inversion count 해준값을 출력해주면 된다.

이 때 각각의 선수들의 inversion count를 기록하는 과정에서 처음엔 index로 접근했는데 선수의 능력이 1~10억이라 인덱스로 접근해서는 안되고, 그 다음엔 map으로 접근했는데 map역시 결국 logN의 시간이 필요하므로 시간초과가 났다. 그래서 그냥 각각의 선수들을 객체로 관리하여 바로바로 count를 업데이트하고 마지막에 한번에 출력하도록 했다.

/*
	21.01.12
	BOJ 2517 : 달리기 (https://www.acmicpc.net/problem/2157)
	inversion count
*/
#include <bits/stdc++.h>
using namespace std;

class Runner {
public:
	int stat;
	int inversion;
	int position;
};

Runner arr[500001] = { 0 };
Runner temp[500001] = { 0 };

void merge(int left, int right)
{
	int mid = (left + right) / 2;

	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i].stat >= arr[j].stat)
			temp[k++] = arr[i++];
		else {
			arr[j].inversion += mid - i + 1;
			temp[k++] = arr[j++];
		}
	}

	int tmp = i > mid ? j : i;

	while (k <= right) temp[k++] = arr[tmp++];

	for (int i = left; i <= right; i++) arr[i] = temp[i];
}

void partition(int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2;
		partition(left, mid);
		partition(mid + 1, right);
		merge(left, right);
	}
}

bool cmp(Runner& a, Runner& b) {
	return a.position < b.position;
}

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

	int N;
	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> arr[i].stat;
		arr[i].inversion = 0;
		arr[i].position = i;
	}

	partition(1, N);

	sort(arr, arr + N + 1, cmp);

	for (int i = 1; i <= N; i++) {
		cout << arr[i].position - arr[i].inversion << '\n';
	}

	return 0;
}