[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2012번, 등수 매기기

문제 링크

2012번: 등수 매기기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N명의 예상 등수와  실제 등수의 불만도는 | A - B |로 수치화할 수 있다. 

2. N명의 실제등수는 임의로 설정한다.

3. N명의 불만도의 합이 최소가 되는 값을 결과로 출력합니다.

4. 동석차는 존재하지 않습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 예상등수 기준 오름차순 정렬 후, 예상등수 1등부터 순차적으로 실제순위를 선정합니다.

 

3. N명에게 모두 실제등수를 선정했을 때 불만도의 합을 결과로 출력합니다.

 

 

실제 순위 선정

 

 

불만도의 합이 최소가 되려면 예상 등수가 실제 등수가 차이가 최대한 최소가 되도록 실제 등수를 선정해야합니다.

 

동석차가 존재하지 않기 때문에 항상 1 ~ N등이 존재하기 때문에

 

예상순위가 높은 사람은 실제 순위도 높은 순위로 주어져야합니다.

 

그래서 예상 등수를 오름차순 정렬한 뒤 순차적으로 1등부터 실제등수를 부여하였을 때

 

불만도의 합이 최소값이 될 수 있습니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 5

 

예상 등수

사람 1	사람 2	사람 3	사람 4	사람 5
1	5	3	1	2

 

2. 예상등수 기준 오름차순 정렬 후, 예상등수 1등부터 순차적으로 실제순위를 선정합니다.

 

예상 등수 기준 오름차순 정렬!

 

사람 1	사람 4	사람 5	사람 3	사람 2
1	1	2	3	5

 

순차적으로 실제순위 선정!

	사람 1	사람 4	사람 5	사람 3	사람 2
예상 등수	1	1	2	3	5
실제 등수	1	2	3	4	5
불만도	|1 - 1| = 0	|1 - 2 | = 1	|2 - 3| = 1	|3 - 4| = 1	|5 - 5| = 0

 

3. N명에게 모두 실제등수를 선정했을 때 불만도의 합을 결과로 출력합니다.

 

0 + 1 + 1 + 1 + 0 = 3

 

3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• Arrays.sort를 이용해서 예상 등수 기준 오름차순 정렬하였습니다.
• 예상 순위가 높은 사람부터 실제 순위 1등을 부여해서 불만도의 값들을 구합니다.
• 실제 순위가 모두 부여된 뒤 불만도의 합을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        //N명의 예상 등수 저장
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(br.readLine());
        Arrays.sort(arr);	//예상 등수 기준 오름차순 정렬
        long answer = 0;	//최악의 경우 Int형의 범위를 초과하기 때문에 long으로 설정!
        //예상등수 높은 것부터 등수 선정 진행 및 불만도 더하기
        for(int i=0;i<N;i++)
            answer += Math.abs(arr[i] - (i+1));
        bw.write(answer + "");	//불만도의 합 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}