[JAVA] 2012번 - 등수 매기기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

문제 아이디어)

불만도의 합을 최소로 해야한다에서 힌트를 찾을 수 있다.

다시 말해 즉, 최대한 본인이 적은 등수를 그대로 사용하면 불만도를 최소로 할 수 있다.

여기서 바로 정렬을 쓰면 될 것같다고 생각해서 정렬로 풀었다.

 

1. 배열을 오름차순으로 정렬한다.

그리고 각 배열의 인덱스-배열의 값 의 절댓값들을 더해주면 끝!

 

 

 

 

시간복잡도

배열을 오름차순으로 정렬하는건 O(NlogN)이다.

N은 최대 500,000이므로 O( 6,561,182)으로 2초안에 가능하다.

 

 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1.배열에 입력받고 정렬

-> 인덱스를 1부터 시작했다 0등은 존재하지 않으니까 계산하기 쉽도록!

for(int i=1; i<=n; i++) {
        	arr[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(arr);

 

2. 불만도 더하기

절댓값 씌워서 인덱스-배열의 값을 하면 된다

즉 실제등수-본인예상 등수 이다.

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

 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

1회차 시도

-> int형으로 했다가 틀렸습니다가 떴다. 

왜 틀렸는지 보다가 알고리즘은 틀린게 없는데 설마 자료형때문인가 생각했는데 역시나 였다.

최악의 경우 최대 500,000명의 학생이 참여가능하다. 

이 학생들의 등수를 모두 더하면 1, 2, ,,,, 500,000등까지 존재한다.

얘네들을 다 더하면 (500,000*500,001)/2

125,000,250,000이다. int의 범위를 초과한다. 

 

정답 코드

-> sum의 자료형을 long으로 바꿔주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

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