[백준] 1758번. 알바생 강호(JAVA)

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

---

문제

---

풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        Integer[] tip = new Integer[N];

        for(int i = 0; i < N; i++){
            tip[i] = sc.nextInt();
        }

        int i = 1, j = 0;
        long sum = 0;

        Arrays.sort(tip, Collections.reverseOrder());
        while(j < N){
             if(tip[j] - (i - 1) > 0) {
                 sum += tip[j] - (i - 1);
                 i++;
                 j++;
             }else{
                 j++;
             }
        }

        System.out.println(sum);

    }
}

 

 문제를 처음 접근할 때 최대 인원에게 팁을 받는게 유리하다고 생각하여 배열 정렬을 오름차순으로 진행하였다.

 

 예를 들면 3 2 3 4 와 같은 경우 2 3 3 4로 정렬하여 2,2,1,1의 돈을 받게한 것이다. 이때의 기대값은 6이 된다. 하지만 4 3 3 2의 경우로 배열하게 된다면 4, 2, 1로 7의 기대값을 갖게 된다. 따라서 내림차순 정렬을 하여 값을 계산하는 것이 옳다.

 

 문제는 자바의 Arrays.sort를 이용하여 내림차순 정렬을 하고 싶은 경우에는 int[]의 경우 불가능하고, Integer[]클래스를 이용한 뒤에 Colletions.reverseOrder()를 사용하여야 한다는 부분이다.