[그리디] - S3_2012_등수매기기

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

2012번: 등수 매기기

 

📌 - 처음 생각한 풀이

1. 예상 등수를 정렬
2. 1씩 증가하면서 예상 등수랑 차이를 더함

 

- 풀이가 분명히 맞다고 생각해서 제출을 했는데 틀림

- 숫자를 보니 50만까지 증가할 수 있는데 최악의 경우 에상등수와 실제 등수의 차이가 최대치로(ex - 예상등수 50만등, 실제 1등) 날 경우가 50만개 있는 경우 int타입을 벗어나서 틀리게 됨

 

📌- 풀이

1. 예상 등수를 정렬
2. 1씩 증가하면서 에쌍 등수랑 차이를 더 함
3. 결과 값의 자료형을 long으로 선언

앞으로 시간 복잡도, 메모리 초과, 자료형을 더욱 확실하게 판단할 필요가 있을 것 같다.

 

🔥 - Java 코드

 

package S3_2012_등수매기기;

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

public class Main {
        public static int n;
        public static long count;
        public static int[] arr;

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());


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

        for(int i=0;i<n;i++){
            count += Math.abs((i+1)-arr[i]);
        }

        System.out.println(count);



    }

}