백준 2517번 : 달리기 (c++)

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

2517번: 달리기

문제

KOI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 

각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다. 예를 들어, 4번째로 달리고 있는 평소 실력이 7인 선수는 그 앞에서 달리고 있는 선수들 중 평소 실력이 2인 선수만 앞지르는 것이 가능하고 평소실력이 8과 10인 선수들은 앞지르는 것이 불가능하므로, 최선의 등수는 3등이 된다.

선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산하는 프로그램을 작성하시오.

입력
첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다.  

출력
각 선수의 최선의 등수를 나타내는 정수 N개를 입력에 주어진 선수 순서와 동일한 순서로 한 줄에 하나씩 출력한다.

예제 입력 1 
8
2
8
10
7
1
9
4
15
예제 출력 1 
1
1
1
3
5
2
5
1

#include <iostream>

using namespace std;

struct runner {
	long value;
	int position;//최초 시작시 자기 position
};

int N;
runner nums[500000];
runner temp[500000];
int ranks[500000]; //1,2,3,4,5,6,7,8 ranks[runner.position] ==> count;

void merge(int s, int m, int e) {
	int p1 = s, p2 = m + 1;
	int k = s;
	while (p1 <= m && p2 <= e) {
		if (nums[p1].value <= nums[p2].value) {
			temp[k++] = nums[p1++];
		}
		else {
			//뒤에서 앞으로 넘어오는 경우
			int count = p1 - s;
			ranks[nums[p2].position] -= count;
			temp[k++] = nums[p2++];
		}
	}

	while (p1 <= m) {
		temp[k++] = nums[p1++];
	}
	while (p2 <= e) {
		//뒤에서 앞으로 넘어오는 경우
		int count = p1 - s;
		ranks[nums[p2].position] -= count;
		temp[k++] = nums[p2++];
	}
	for (int i = s; i <= e; i++)
	{
		nums[i] = temp[i];
	}
}

void mergeSort(int s, int e) {
	if (s < e) {
		int mid = (s + e) / 2;
		mergeSort(s, mid);
		mergeSort(mid + 1, e);
		merge(s, mid, e);
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> N;
	int a=0;
	for (int i = 0; i < N; i++)
	{
		cin >> a;
		nums[i] = { a,i };
		ranks[i] = i+1;
	}
	mergeSort(0, N - 1);
	for (int i = 0; i < N; i++)
	{
		cout << ranks[i];
		if (i != N - 1) {
			cout << "\n";
		}
	}
	return 0;
}