[백준] 2012번 : 등수 매기기 – JAVA [자바]

[Silver III] 등수 매기기 - 2012

문제 링크

성능 요약

메모리: 57256 KB, 시간: 872 ms

분류

그리디 알고리즘, 정렬

문제 설명

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

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

 

---

• 문제 풀이

이 문제는 불만도의 합이 최소가 되는 경우를 찾으면 쉽게 풀 수 있다.

입력 받는 순서가 학생들의 등수이고, 이 순서(index)와 그 학생의 예상 등수의 차이가 적으면 된다.

 

예를 들어, 위의 예제로 설명하자면

 

1. 첫 번째 입력된 학생의 예상 등수는 1이고, 현재 위치한 등수 또한 1이기 때문에 불만도는 0이다.
2. 두 번째 입력된 학생의 예상 등수는 5이고, 현재 위치한 등수는 2이기 때문에 불만도는 3이다.
3. 세 번째 입력된 학생의 예상 등수는 3이고, 현재 위치한 등수 또한 3이기 때문에 불만도는 0이다.
4. 네 번째 입력된 학생의 예상 등수는 1이고, 현재 위치한 등수는 4이기 때문에 불만도는 3이다.
5. 다섯 번째 입력된 학생의 예상 등수는 2이고, 현재 위치한 등수는 5이기 때문에 불만도는 3이다.

입력 받은 대로 불만도의 합을 구하면 9이다.

하지만 위의 설명 대로 현재 위치한 등수와 예상 등수의 차이가 적게 하려면,

즉 오름차순으로 정렬되면 불만도가 최소가 될 것이다.  → 1 1 2 3 5

 

1. 첫 번째 입력된 학생의 예상 등수는 1이고, 현재 위치한 등수 또한 1이기 때문에 불만도는 0이다.
2. 두 번째 입력된 학생의 예상 등수는 1이고, 현재 위치한 등수는 2이기 때문에 불만도는 1이다.
3. 세 번째 입력된 학생의 예상 등수는 2이고, 현재 위치한 등수 또한 3이기 때문에 불만도는 1이다.
4. 네 번째 입력된 학생의 예상 등수는 3이고, 현재 위치한 등수는 4이기 때문에 불만도는 1이다.
5. 다섯 번째 입력된 학생의 예상 등수는 5이고, 현재 위치한 등수는 5이기 때문에 불만도는 0이다.

따라서 오름차순으로 정렬한 학생들의 불만도의 합은 3이고 최소가 되는 경우이다.

---

• 코드

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] data = new int[n];

        // 데이터 입력
        for(int i = 0; i < n; i++){
            data[i] = Integer.parseInt(br.readLine());
        }

        // 오름차순 정렬
        Arrays.sort(data);

        long sum = 0;
        for(int i = 0; i < n; i++){
            // 절댓값 주의!! (음수가 될 수 있기 때문에)
            sum += Math.abs((i+1) - data[i]);
        }
        System.out.println(sum);
    }
}

※ 음수가 될 수 있기 때문에 절댓값을 빼먹으면 안된다.

※ sum의 자료형이 int가 아닌 long이어야 한다. (1 ≤ N ≤ 500,000)