[백준] 2012번 등수 매기기 (그리디알고리즘_JAVA)

자료형을 생각하지 못해 

결국은 질문 게시판을 보고 푼 문제..

 

아직도 int와 long때문에 몇시간을 헤매다니  ╯︿╰

더 단련이 필요한 거 같다!

 

 

---

문제

 

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

2012번: 등수 매기기

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 그리디 알고리즘

가장 먼저 생각한 방법이다.

틀려서 순열과 dp 방법으로도 풀어봤지만, 시간초과와 메모리초과가 발생해서 다시 처음부터 생각해봤더니

자료형이 맞지 않아 틀렸던 것이다.

 

그리디 알고리즘 방식은 그때 그때 최적의 방법을 선택하는 알고리즘으로,

이 문제에 대입해보면 각자 자신이 생각하는 등수 배열을 입력받고 오름차순으로 정렬해준다.

그 후 가장 높은 등수를 예상한 사람부터 1등 - 마지막 등수와 비교하고 절대값을 더해준다.

 

여기서 틀린 이유는 최대 값이 500000이라, 모든 사람이 자신이 500000등이라고 생각할 경우,

답이 21억이 넘기 때문에 int형이 아닌 long형으로 해야 했다.

 

 

---

코드

import java.util.Arrays;
import java.util.Scanner;

public class Test_2012_등수매기기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		//점수 배열 생성 및 값 입력받기
		int[] arr = new int[n];
		for(int i=0; i<arr.length; i++) {
			arr[i]=sc.nextInt();
		}
		
		//정렬
		Arrays.sort(arr);
		
		//불만도 합 구하기
		long result=0;
		for(int i=0; i<arr.length; i++) {
			result += Math.abs(arr[i]-(i+1));
		}
		
		//출력
		System.out.println(result);
	}
}

 

 

 

(❁´◡`❁)

끝!