[백준] 1758- 알바생 강호

문제링크: 바로가기

# 그리디 알고리즘 # 정렬

스터디 과제로 풀었다가 틀린 문제인데, 스터디원이 다 맞았는데 왜 틀린지를 모르겠다고 피드백 줬었다. 12일 후인 오늘 그리디 알고리즘 연습삼아 복습 겸 풀어봤다. 

구글링한 부분은 Array.Sort를 Reverse, 즉 내림차순으로 하는 부분이다. Collection과 Comparator 인터페이스를 사용하면 된다. 유의할 점은 data type을 primitive(ex.int)가 아닌 객체로 지정해줘야 한다는 것이다. (ex.Integer)

그리고 이번에도 보기만 해도 짜증이 나는 틀렸습니다! 가 떴는데 그 이유를 알아냈다. 받을 수 있는 팁 최대값 변수 data type을 int로 선언했기 때문이다. 이놈의 함정은 내가 문제를 제대로 못 읽고 파악 못한 탓이겠지..

입력 부분을 잘 읽어보면 사람 수 N(100,000 이하)와 팁(100,000이하)이 주어진다고 나와있다. 따라서 100,000명의 사람이 100,000을 갖게 되면 팁의 최대는 100억이 된다. 따라서 int의 범위인 약 20억을 (-2147483648 ~ 2147483647)넘는다... 오버플로우 발생

변수 total 을 long으로 바꿔주니 맞았습니다! 가 잘떴다. 휴우

그리고 블로그를 보다가 알게 되었는데 배열을 오름차순으로 정렬했기 때문에 음수가 나오면 반복문을 즉시 종료(break)해서 불필요한 연산을 줄일 수 있다. 

또한 변수 초기화 할 때 재사용할 변수가 아니라면 더 간결하게 작성할 수 있다는 사실도 배웠다. 예를 들어 아래와 같이 줄여 쓸 수 있다면 줄이는 게 보기에도 좋고, 나은 코딩 습관이라고 생각된다.

  //중복이 있는 코드
 	for(int i = 0; i < n; i++) {
    	int tip = sc.nextInt();
 		tipArr[i] = tip;
	 }

  //간결한 코드
   	for(int i = 0; i < n; i++) {
    	tipArr[i] = sc.nextInt();
     }

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Starbox_1758 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //사람 수
        int n = sc.nextInt();
        //최대 팁
        long total = 0;
        Integer[] tipArr = new Integer[n];

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

        //Arrays sort 하는 법: 객체로 지정하면 됨 (Integer)
        Arrays.sort(tipArr, Comparator.reverseOrder());

        for(int i = 0; i < n; i++) {
            if(tipArr[i] - i <= 0) {
                break;
            }
            total += tipArr[i] - i;
        }

        System.out.println(total);
        sc.close();


    }
}