[백준/BOJ] 2012. 등수 매기기 [Silver 3]
- 등수 매기기
문제출처 : 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;
}
Author And Source
이 문제에 관하여([백준/BOJ] 2012. 등수 매기기 [Silver 3]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jychan99/백준BOJ-2012.-등수-매기기-Silver-3-시간초과저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)