[알고리즘] 그리디 문제 풀이 2

백준 2012

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


class Main{
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long sum = 0;
        int 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++){
            sum += Math.abs((i+1)-arr[i]);
        }
        System.out.println(sum);
    }
}

얻어갈 점:

• 일단 해당 문제에서 그리디 알고리즘을 사용해야한다는 것 자체를 인지를 못했다.(키워드는 "가장 불만이 적게")
• 그리디 문제 안 푼지 좀 돼서 그런 것 같으니 이 글 정리 후 그리디 알고리즘 복습하기.
• long sum => 자료형을 처음에 int로 썼는데 예시를 잘 보면 주어진 N 최대가 500,000 예상 등수 범위 500,000이니 모두가 1등으로 적어 내면 i가 0부터 시작한다 가정했을때 |1-(i+1)| * 500,000 이기 때문에 int 자료형 범위를 벗어난다!
• 간단한 문제에서 내가 직접 sort 구현 보다 Arrays.sort() 이용하기