[BAEKJOON] 2012 등수 매기기

문제 요약

• 알고리즘 분류: 그리디
• 난이도: Silver3
• 문제내용:
  • 실제 성적 등수와 학생 예상 등수 최소 차이를 구해라

• 사이트: https://www.acmicpc.net/problem/2012

2012번: 등수 매기기

문제풀이

 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑에 사이트에 참조하면된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

문제 접근방법 

 예상 등수와 실제 등수를 차이를 최소화하기 위해서는 먼저 정렬을 하면된다. 정렬 한뒤에는 예상등수와 예상 등수 위치인(index + 1)차이를 구하기만 하면 불만도가 최소가 된다. 위 예제로 다시 설명한다면....

  위 그림에서 보면 1, 5,3, 1, 2를 1, 1, 2, 3, 5로 정렬 한다음 아래 처럼 실제 등수와 예상 등수 차이의  합을 구하면된다.

• 1 - 1
• 2 - 1
• 3 - 2
• 4 - 3
• 5 - 5  

그러면 예제의 답은 3이 나온다.

 

Code

Python

import sys
input = sys.stdin.readline
ranks = sorted([int(input()) for _ in range(int(input()))])
count = 0
for index, ranks in enumerate(ranks):
    count += abs(ranks - index - 1)    
print(count)

Java

 여기서 count변수를 보면 long으로 선언이 되어있다. 개수가 Integer크기보다 클수 있기 때문에 long  타입으로 선언 해야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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());
		int[] ranks = new int[N];
		for(int i = 0; i < N; i++) {
			ranks[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(ranks);
		long count = 0;
		for(int i = 0; i < N; i++) {
			count += Math.abs(ranks[i] - 1 - i);
		}
		System.out.println(count);
	}
	
}