[백준] 2012 등수 매기기 with Python

📌 BOJ 2012 등수 매기기

💡 조건

1. 2007년 KOI에 N명의 학생들이 참가하였다. 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

2. 1등부터 N등까지 동석차 없이 등수를 매겨야한다. 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

3. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다.

4. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

5. 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다.
   예상 등수는 500,000 이하의 자연수이다.

6. 그리디알고리즘, 정렬 유형의 문제

🖥 소스 코드

from sys import stdin

n = int(stdin.readline())
s = []
for i in range(n):
    s.append(int(stdin.readline()))

s.sort()
ans = 0
for i in range(1, n + 1):
    ans += abs(i - s[i - 1])
print(ans)

🔖 예제 및 실행결과

예제

5
1
5
3
1
2

실행결과

3

⌨️ 문제 풀이

1. 예상 등수를 입력받아 차례대로 list s 에 저장한다.

2. list s 를 정렬 한 뒤, ans 변수를 0으로 초기화 하고, 1부터 n + 1까지 순회하면서 예상등수에 해당하는
   불만도를 계산하여 ans에 저장해준다.

3. ans를 출력한다.

4. 불만도를 정렬하여 실제 등수와 비교하여 계산을 하면 최솟값을 구할 수 있다.

💾 느낀점

1. 정렬하여 문제를 푸는 간단한 문제였습니다.
2. 골드 5 난이도 정도의 그리디에 취약한 모습을 보이는 것 같아 연습이 많이 필요할 것 같습니다.