2012번 : 등수 매기기

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

2012번: 등수 매기기

 

 

문제

 

 

코드

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

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());
        ArrayList<Integer>a = new ArrayList<>(n);
        for(int i=0;i<n;i++) {
            a.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(a);
        long result=0;
        int rank=1;
        for(int i=0;i<n;i++) {
            result += Math.abs(a.get(i) - (rank++));
        }

        System.out.println(result);
    }
}

 

 

해결방법

1 5 3 1 2 예상 등수
1 1 2 3 5 예상 등수 (정렬)
1 2 3 4 5 실제 등수
0 1 1 1 0 불만도

단순히 예상 등수를 오름차순 정렬하여 반복문을 돌려 불만도를 구하면 되는 쉬운 문제이다. 하지만 "틀렸습니다."가 떴다.

반례를 찾으려고 생각을 계속 해봤는데 결국 찾지 못했다.

틀린 이유는 아래와 같이 최악의 해가 들어왔을 때 불만도(result)가 int형 범위를 넘을 수 있기 때문이었다.

  input
     n = 500,000
     a[i] = {1, 1, ..., 1}

     result = 0 + 1 + 2 + ... + 499,999

고로 불만도의 타입을 long형으로 바꿔야 했다. 

타입을 잘 생각하자..