[Silver III] 등수 매기기 - 2012

문제 링크

성능 요약

메모리: 54308 KB, 시간: 840 ms

분류

그리디 알고리즘, 정렬

문제 설명

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

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

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

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

입력

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

출력

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

---

• 내 코드

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] arr;
    static int[] sorted;
    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        sorted = new int[n];
        for (int i = 0; i < n; i++) {
            sorted[i] = i + 1;
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        sumBulmando();
    }

    private static void sumBulmando() throws IOException {
        long ans = 0;
        for (int i = 0; i < arr.length; i++) {
            ans += Math.abs(arr[i] - sorted[i]);
        }
        System.out.println(ans);
    }
}

• 내 풀이

문제분류가 그리디, 정렬인걸확인 후
I/O static 으로 선언해주고
입력받을 int arr
1등부터 N등 까지의 등수를 담아줄 sorted int 배열이 껍데기를 선언해줌
n을 입력받아주고
arr, sorted를 init해줍니다 배열의크기는 당연히 학생들의 수인 N입니다.
문제에서 제시했듯이 학생들의 예상 석차를 입력받습니다 반복문을통해서
arr, sorted index에 접근하기 위해서 0 ~ n-1
sorted 배열은 1~N 의 정보를 담아야하니 i + 1 로 지정
듀얼피봇 퀵정렬(Dual-Pivot QuickSort) 알고리즘을 사용하는 Arrays class의 sort메서드를 사용해서 정렬함
 *
듀얼피봇 퀵정렬 (inserting sort(삽입정렬) + quick sort(퀵정렬)) 아직 퀵정렬을 이해하는중
 *
정렬 후 메인 로직 진입
출력값인 ans 변수를 long으로 만들어주고
왜 long?
문제에서 N의 범위가 500,000 인데, 만약 모든 학생이 자신의 등수를 1로 예상할경우,
|1-500,000| x 500,500 이 되어서 int의 범위를 벗어난다.
|arr[index] - sorted[index]| 를 ans에 더해주고 출력해준다.