[백준/BOJ] 2012. 등수 매기기 [Silver 3]

2012. 등수 매기기

문제출처 : https://www.acmicpc.net/problem/2012

code

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void QuickSort(int arr[],int start,int end)
{
	if (start >= end)
		return;
	int piv = start, left = start + 1, right = end, temp;
	while (left <= right)
	{
		while (left <= end && arr[left] <= arr[piv])
			left++;
		while (right > start && arr[right] >= arr[piv])
			right--;
		if (left > right)
		{
			temp = arr[right];
			arr[right] = arr[piv];
			arr[piv] = temp;
		}
		else
		{
			temp = arr[right];
			arr[right] = arr[left];
			arr[left] = temp;
		}
	}
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int main()
{
	int N, i;
	long long complain = 0;
	int* rank;
	scanf("%d", &N);
	rank = (int*)malloc(N * sizeof(int));
	for (i = 0; i < N; i++)
		scanf("%d", &rank[i]);
	QuickSort(rank, 0, N-1);
	for (i = 0; i < N; i++)
		complain += abs((i+1) - rank[i]);
	printf("%lld", complain);
	free(rank);
	return 0;
}

오름차순 정렬후 순위-배열값의 절대값을 불만도에 더해주는 방식으로 짰다.
알고리즘은 맞는것 같은데 45%에서 계속 시간 초과가 난다 ㅠㅠ

C++로 해결했다. 알고리즘은 동일하게 적용했다.

code

#include <iostream>
#include <algorithm>
using namespace std;

int Rank[500000] = { 0 };
int main()
{
	int N, i;
	long long complain = 0;

	cin >> N;
	
	for (i = 0; i < N; i++)
		cin >> Rank[i];

	sort(Rank, Rank + N);

	for (i = 0; i < N; i++)
		complain += abs((i + 1) - Rank[i]);

	cout << complain;
	
	return 0;
}