등수의 불만도를 최소화 하기 위해서는 각 예상등수를 오름차순 정렬하여 최대한 예상등수와 등수와의 차이를 줄여야한다.
예상 등수를 오름차순하여 grade를 1부터 비교하며 불만도의 합을 구하는 것이다.
이때 각 등수의 불만도는 최대 1000000, 학생의 수는 500000이므로 1000000*500000은 long타입
을 사용해야한다.
public class 등수매기기 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
//예상 등수
int[] anticipateGrade = new int[N];
for(int i=0;i<N;i++){
anticipateGrade[i] = Integer.parseInt(br.readLine());
}
//예상 등수 오름차순 정렬
Arrays.sort(anticipateGrade);
long answer=0;
int grade=1;
for(int i=0;i<N;i++){
//예상등수 - 등수의 차이로 최소 불만도의 합 구하기
answer += Math.abs(anticipateGrade[i]-grade);
grade++;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
}