[BOJ] 2012 - 등수 매기기

클릭 시 해당 문제로 이동

 

💬 문제 설명

N명의 학생이 "나는 ○등 하고 싶어요!"라고 예상 등수를 제출한다. 하지만 모든 학생의 예상이 들어맞을 수는 없다.

각 학생의 예상 등수와 실제 등수 간의 차이의 총합을 최소화하도록 학생들에게 실제 등수를 부여하자.

 

📌 주의 사항

• 학생 수 N: 1 ≤ `N` ≤ 500,000
• 예상 등수: 1 이상 `N` 이하의 정수
• 출력: 학생들의 예상 등수와 실제 등수의 차이의 총합의 최솟값

 

---

👌 문제 풀이

이 문제는 Greedy(탐욕 알고리즘)로 해결할 수 있다.

 

 핵심 아이디어

• 정렬한 예상 등수와 1등부터 차례로 부여하는 실제 등수를 매칭해서 차이의 총합을 최소화할 수 있다.
• 예를 들어 예상 등수가 [1, 2, 2, 6]이라면,
  정렬 후 [1, 2, 2, 6]와 [1, 2, 3, 4]를 비교한다.

 

---

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 등수매기기 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int[] array = new int[N];
        
        for (int i = 0; i < N; i++) {
            array[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(array);  // 예상 등수 정렬
        
        long result = 0;  // 총 불만도는 매우 클 수 있으므로 long 사용
        
        for (int i = 0; i < N; i++) {
            result += Math.abs(array[i] - (i + 1));  // 예상등수 - 실제등수
        }
        
        System.out.println(result);
    }
}

---

🧠 회고

❌ 틀렸습니다

⚠️ 주의 사항: int vs long

• 문제에서 N이 최대 500,000이므로,
  최악의 경우 (500,000 - 1)^2 = 약 2.5 * 10^11까지 총합이 커질 수 있다.
• `int`의 범위는 약 ±21억 (-2,147,483,648 ~ 2,147,483,647)
• 따라서 `int result = 0`으로 작성하면 오버플로우 발생 가능 → 틀린 답 출력
• 반드시 `long result = 0`으로 선언해야 한다!

 

처음엔 예상 등수 배열과 1 ~ N의 실제 등수를 단순히 맞춰보면 되지 않을까 했지만
정렬을 통해 가장 가까운 등수끼리 매칭하는 것이 가장 불만을 줄일 수 있는 방법이라는 걸 깨달았다.
또한 문제 자체는 쉬웠지만 int로 합계를 계산하면 틀린 정답이 나오는 예외를 만나서
자료형의 기본 개념의 중요성을 다시 한번 느낄 수 있었다.

 

---

✅ 배운 점

• Greedy 알고리즘의 기본 전략: "정렬 후 순차 매칭"
• 자료형 선택의 중요성 ≫ 연산이 커질 수 있는 누적합 문제에서는 `long` 고려하기!
• 문제의 조건(N의 범위 등)은 단순한 정보가 아니라 자료형 결정의 근거가 될 수 있음