[백준] 2012 등수 매기기 - 그리디(Greedy, 탐욕법) + 정렬(Sort) JAVA

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

코드설명

그리디(Greedy, 탐욕법) + 정렬(Sort) 문제입니다.

 

문제에서 숫자를 정렬해서, 각 숫자와 가장 가까운 값으로 차례대로 등수를 정해주는 것을 떠올리는 건 어렵지 않습니다. 직관적으로, 각 등수에서 가장 가까운 숫자로 등수를 매겨야만 최소값을 구할 수 있음을 알 수 있습니다.

 

실수했던점은, 불만도가 int형의 범위인 2^31(약 21억)의 범위를 넘어갈 수 있다는 점입니다.

N이 최대 500,000 이고, 가능한 최대 등수도 500,000 입니다. 이떄 모두의 예상등수가 1 이라면, 50,000 * 50,000 이 최소 불만도가 됩니다. 이는 2,500,000,000 = 25억으로 long 형 자료형을 사용합니다.

코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static int N, M;
    public static long answer = 0;
    public static int[] arr;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		N= Integer.parseInt(st.nextToken());
		arr = new int[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		
		for(int i=1; i<=N;i++) {
			answer += Math.abs(arr[i - 1] - i);
		}
		System.out.println(answer);
		
	}
    
    
}