[프로그래머스] LV1. 과일 장수

프로그래머스 LV1 목록
1. 추억 점수
2. 바탕화면 정리
3. 달리기 경주
4. 과일 장수

문제

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.

한 상자에 사과를 m개씩 담아 포장합니다.
상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.
과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.

(최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8
사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

제한사항
3 ≤ k ≤ 9
3 ≤ m ≤ 10
7 ≤ score의 길이 ≤ 1,000,000
1 ≤ score[i] ≤ k
이익이 발생하지 않는 경우에는 0을 return 해주세요.

해결 과정

Step1) 사과가 몇 개 있는지 파악하여 몇 개의 상자를 만들 수 있는지 파악한다.
Step2) 주어진 score 배열을 오름차순으로 정렬한다.
Step3) 정렬된 score 배열의 뒤에서부터 상자를 만들어나간다. --> 뒤에서 만들어야 상자에 들어가는 가장 낮은 가격의 사과가 전체 사과 중 점수가 큰 편에 속하기 때문에 최대 가격을 구할 수 있다.

위의 절차대로 작성한 코드는 아래와 같다.

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int box_num=(score.length)/m;
        
        
        for(int j=0;j<score.length-1;j++){
            for(int i=0;i<score.length-1-j;i++){
               
                if(score[i]>score[i+1]){
                    int temp=score[i];
                    score[i]=score[i+1];
                    score[i+1]=temp;
                }
            }
        }
        int s=score.length-1;
       
        for(int i=0;i<box_num;i++){
            answer+=score[s-m+1]*m;
            s-=m;
        }
        
        return answer;
    }
}

주어진 score 배열을 오름차순으로 정렬할 때 버블 정렬을 이용하였다. 하지만 버블 정렬은 데이터가 많을 경우 시간 소모가 크다. 따라서 위의 코드로는 시간 초과로 성공하지 못했다.

다른 오름차순 정렬 알고리즘을 찾다가 자바에는 sort 함수를 지원한다는 것을 알게 되었다.
import java.util.Arrays를 작성한 후 sort 함수를 이용하면 int자료형과 String 자료형을 자동으로 오름차순 정렬해준다.

이를 발견하니 코드가 더 간단해졌고 아래처럼 Arrays.sort(score); 한 줄만 추가함으로써 코드가 완성되었다.

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int box_num=(score.length)/m;
        
        Arrays.sort(score);
        int s=score.length-1;
       
        for(int i=0;i<box_num;i++){
            answer+=score[s-m+1]*m;
            s-=m;
        }
        
        return answer;
    }
}