[백준 시리즈] 2012번 : 실버3 - 등수 매기기 / Python

제목 : 등수 매기기

출처 : 백준 /  2012번: 등수 매기기 (acmicpc.net)

사용 자료구조&알고리즘 : 그리디, 정렬

 

문제 설명

1. 모든 학생의 시험 정보를 날려 1등부터 N등까지 동석차 없이 등수를 임의로 매겨야 한다. 

2. 예상 등수와 결과 등수의 차를 불만도라고 할 때, 불만도의 합의 최소가 되도록 등수를 매기려고 한다.

3. 불만도 합의 최솟값을 구해라.

 

제한

시간 제한 : 2초

메모리 제한 : 256 MB

N (1<= N <= 500,000)

예상 등수는 500,000 이하의 자연수이다.

 

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

N의 크기가 10,000 이상이기 때문에 O(NlogN) 이하 시간복잡도가 요구된다.

 

2단계 : 핵심 아이디어는 무엇인가?

예상 등수를 정렬하고 정렬된 등수대로 실제 등수를 부여하여 불만도를 계산할 때, 예상 등수와 실제 등수의 차의 총합이 최소가 될 수 있다. O(NlogN)만에 문제를 해결할 수 있다.

 

정답 코드

n = int(input())
arr = [int(input()) for _ in range(n)]
arr_sum = 0

arr.sort()
for i in range(n):
    arr_sum += abs(arr[i] - (i+1))

print(arr_sum)