[백준/Java] 2012번 : 등수 매기기

🌵 문제 분석

https://www.acmicpc.net/problem/2012

N명의 학생들의 예상 등수(A)와 실제 등수(B)의 차이의 총 합이 최소가 되도록 실제 등수를 매겼을 때

불만도의 합을 출력하라.

 

입력 :

N(학생 수)

N개의 예상 등수

🌵 구현 아이디어

❎ 브루트 포스는 시간 초과

브루트 포스로 탐색하면 등수 500,000개마다 500,000명의 학생 중 누가 가장 불만도가 작은지 검사해야 하고 시간 복잡도가 250,000,000,000 > 2억 이므로 2초 안에 연산 불가능하다.

 

뿐만 아니라 아래와 같이 실제 등수를 항상 불만도가 가장 낮은 학생에게 부여하게 되면 

먼저 실제 등수가 부여된 학생들은 불만도가 최소가 될 수 있지만 

앞에서 부여되고 남은 등수를 뒤에 탐색되는 학생들에게 매칭하게 되면 불만도가 얼마나 커질지 알 수 없다.

 

👉🏻 실행 과정

실제 등수 1인 학생 결정하기 -> 학생 N명을 모두 방문하며 불만도가 가장 낮은 수 찾기

실제 등수 2인 학생 결정하기 -> 학생 N-1명을 모두 방문하며 불만도가 가장 낮은 수 찾기

...

실제 등수 500,000인 학생 결정하기 

학생 번호	1	2	3	4	5	불만도
예상 등수	1	5	3	1	2
실제 등수	1	4	3	5	2	5

 

-> 모든 경우를 탐색하면서 예상 등수와 실제 등수 차이가 0인 경우, 0인 경우가 없으면 1인 경우, 1인 경우가 없으면 2인 경우... 순으로 실제 등수가 결정되었지만 나중에 탐색되는 학생들의 불만도를 고려하지 않아서 결국 효율적인 방법이 아님

 

✅ 예상 등수가 작은 학생부터 그리디하게 탐색하기

예상 등수를 오름차순으로 정렬한 후 실제 등수를 1부터 N까지 차례로 부여한다.

예상 등수와 실제 등수가 속도는 다르겠지만 함께 오르므로

모든 학생들의 불만도를 전체적으로 낮출 수 있다.

 

👉🏻 실행 과정

1. 학생을 예상 등수 기준으로 오름차순 정렬하기

2. 실제 등수를 차례대로 부여하기

학생 번호	1	4	5	3	2	불만도
예상 등수	1	1	2	3	5
실제 등수	1	2	3	4	5	3

 

🌵 시간 복잡도

오름차순 정렬 : O(NlogN)

실제 등수 부여하기 : O(N)

 

전체 시간 복잡도는 O(NlogN)+O(N) = 500,005이므로 시간 안에 연산 가능하다.

🌵 알고리즘

그리디

🌵 코드 설계

1. 입력 받기
   1. N 저장
   2. arr 배열에 N개의 예상 등수 저장
2. 예상 등수 정렬
3. arr를 순회하며 차례로 불만도 구하기
4. 불만도 출력

🌵 오답 노트

자료형을 long으로 선언해야 함

🌵 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        long ans = 0;
        long num = 1;
        for(int rank : arr){
            ans += Math.abs(rank-num);
            num++;
        }
        System.out.println(ans);
    }
}