자바(백준) 1758 알바생 강호

오답 노트 & 새로 알게 된 점

해당 문제는 꽤나 애를 먹었다. 문제를 제대로 읽지 않아 손님의 순서를 적절히 바꿨을 때 이 부분을 읽지 않았다.

그래서 문제를 제대로 읽고 음수가 되면 어차피 0원이니까 제일 적은 팁을 주는 사람이 가장 뒤에 있어야 최댓값이 나온다는 생각을 했다. 그래서 Comparator로 내림차순을 사용하려고 하는데, 여기서 또 문제가 생겼다.

Comparator는 기본 자료형에서는 호출되지 않고 Wrapper 클래스에서 호출이 가능하다. (객체) 그래서 이 부분을 잘 몰라 계속 Comparator를 시도했고, 알게 된 후에는 배열을 Integer로 선언하여 문제를 풀었다.

또, 여기서 이제 다 맞은 줄 알고 제출을 했는데 틀렸습니다가 나왔다. 그 이유는 결괏값인 sum의 자료형이 int형이어서이다. 문제를 보면 사람의 수는 최대 99,999이고 팁도 최대 99,999이다. 계산하기 쉽게 둘 다 100,000이라 할 때 만약 100,000 팁을 100,000명이 준다 하면 100,0000,0000으로 21억이 넘어가게 된다. 그래서 long으로 선언해주어야한다.

자세한 건 아래 주석을 참고하자.

 

---

 

코드

package Greedy;
 
//BOJ 1758 알바생 강호
 
import java.io.*;
import java.util.*;
 
public class BOJ1758 {
    static int atoi(String str){
        return Integer.parseInt(str);
    }
    static Integer[] arr;
    //내림차순을 사용하기 위해 Wrapper 클래스로 선언
    //Comparator를 쓰기 위해서는 객체 형태이어야함. 그래서 처음에
    //int형으로 선언하고 왜 Comparator가 안쓰이지라는 생각을 했는데
    //객체로 선언안해서 그랬음. 기본 자료형은 Comparator를 호출할 수 없음.
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int size = atoi(st.nextToken());
        arr = new Integer[size];
 
        for(int i = 0; i < size; i++){
            st = new StringTokenizer(br.readLine());
            arr[i] = atoi(st.nextToken());
        }
 
        //내림차순 정렬
        Arrays.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
 
        System.out.println(sumTip());
    }
    static long sumTip(){
        //여기서 왜 맞왜틀이 나옴.
        //보니까 N이 100,000보다 작은 자연수인데 팁도 100,000보다 작거나 같은 자연수임
        //그래서 100,000 * 100,000 해보면 21억이 넘어서 int형으로 하면 틀림.
        //이것 때문에 시간 오래 걸림. 항상 생각하자.
        long sum = 0;
        for(int i = 0; i < arr.length; i++){
            int tip = arr[i] - i;
            if(tip >= 0) sum += tip;;
        }
        return sum;
    }
}