백준 2012번: 등수 매기기 문제 해설 (Python)

백준 2012번: 등수 매기기 (Python)

---

문제 설명

N명의 학생이 제출한 예상 등수가 주어집니다. 실제 등수는 1등부터 N등까지 중복 없이 매겨져야 하며, 예상 등수와 실제 등수의 차이의 절댓값을 불만도로 정의합니다. 모든 학생의 불만도 합이 최소가 되도록 실제 등수를 배정했을 때, 그 최소 불만도의 합을 구하는 프로그램을 작성해야 합니다.

---

테스트케이스

입력

5
1
5
3
1
2

출력

3

설명

1. 예상 등수를 오름차순으로 정렬하면 → 1 1 2 3 5가 됩니다.
2. 최소 불만도를 위한 실제 등수도 순서대로 매칭하면 → 1 2 3 4 5가 됩니다.
3. 불만도 합계 계산 → |1-1| + |1-2| + |2-3| + |3-4| + |5-5| = 0 + 1 + 1 + 1 + 0 = 3입니다.

---

문제 작동 원리

• 불만도의 합은 ∑ |예상등수[i] - 실제등수[i]|로 계산됩니다.
• 이 불만도 합을 최소화하는 가장 핵심적인 아이디어는, 예상 등수와 실제 등수를 모두 오름차순으로 정렬하여 순서대로 매칭하는 것입니다.
• 이것이 최적의 해를 찾는 방법이라는 것은 교환 논증(Exchange Argument)을 통해 증명할 수 있습니다. 즉, 어떤 두 쌍이 교차되어 매칭될 경우, 그 둘을 올바르게 정렬하여 매칭하는 것이 항상 더 나은(또는 같은) 결과를 가져옵니다.





• 만약 예상 등수 중에 1, 1, 2와 같이 중복된 값이 있더라도, 정렬 후 순서대로 1, 2, 3을 실제 등수로 매기면 최적의 불만도 합을 구할 수 있습니다.
• N의 최대값이 500,000이고 예상 등수가 1부터 500,000까지 주어질 수 있으므로, 불만도 합이 `int` 자료형의 범위를 초과할 수 있습니다. 파이썬의 정수는 크기 제한이 없으므로 오버플로 걱정이 없지만, 다른 언어라면 long long 같은 자료형을 사용해야 합니다.

---

아이디어

1. N명의 예상 등수를 입력받아 리스트에 저장합니다.
2. 저장된 예상 등수 리스트를 오름차순으로 정렬합니다.
3. 정렬된 리스트의 각 원소(예상 등수)에 대해, 순서대로 1, 2, 3, ... N을 실제 등수로 매칭합니다.
4. 매칭된 각 쌍의 차이의 절댓값을 구하여 전체 합계에 더합니다.
5. 계산된 불만도 합을 출력합니다.

---

전체 코드

N=int(input())

arr=[]
for i in range(N):
    arr.append(int(input()))

arr.sort()
answer=0
for i in range(N):
    answer+=abs(arr[i]-(i+1))

print(answer)

---

결론

• 이 문제는 **그리디 알고리즘**과 **정렬**을 활용하여 해결할 수 있습니다.
• **예상 등수를 정렬한 후, 1부터 N까지의 실제 등수와 순서대로 매칭**하는 것이 불만도 합을 최소화하는 가장 효율적인 방법입니다.
• 파이썬에서는 정수 오버플로 걱정 없이 그대로 계산할 수 있습니다.
• 주요 로직인 정렬의 시간 복잡도는 $O(N \log N)$이며, 이는 $N \le 500,000$에서도 충분히 빠르게 동작합니다.