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

문제

과일 장수가 사과 상자를 포장하고 있습니다.
사과는 상태에 따라 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 해주세요. 입출력 예

kmscoreresult

3	4	1, 2, 3, 1, 2, 3, 1	8
4	3	4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2	33

---

풀이

사과를 m개씩 나누어서 최대한 이득이 되는 방향을 구해야 한다. 우선, 어떠한 방식으로 나누어야 최대한 이득이 나올까?
무게가 많이 나가는 것들을 최대한 모아 놓아서 이를 상자로 만들어야 한다.
따라서 정렬이 필요하다.

예외처리를 해야 하는 부분은 남은 사과가 m보다 작은 경우, 이때는 상자를 만들 수가 없으므로 버려야 한다.

for(int i = score.length - 1; i >= 0; i -= m) {
            
            if (i < m - 1) {
                break;
            }
            
            int subNum = k;
            int countNum = i;
            for(int j = 0; j < m; j++) {
                if (score[countNum] < subNum) {
                    subNum = score[countNum];
                }
                countNum--;
            }
            
            answer += subNum * m;

        }

2중반복을 하는 이유는 m개씩의 사과를 추출하여 거기에서의 최소값을 추출하는 것인데,
사실 이미 정렬을 했으므로 저 부분을 제외하고 m개씩 자른 부분에서 맨 앞의 사과의 무게를 가져오면 그것이 최솟 값이기 때문에 저부분은 삭제해도 무방하다.

 

import java.lang.*;
import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        Arrays.sort(score);
        
        for(int i = score.length - 1; i >= 0; i -= m) {
            
            if (i < m - 1) {
                break;
            }
            
            int subNum = k;
            int countNum = i;
            for(int j = 0; j < m; j++) {
                if (score[countNum] < subNum) {
                    subNum = score[countNum];
                }
                countNum--;
            }
            
            answer += subNum * m;

        }
        
        return answer;
    }
}

 

 

https://github.com/Win-9/Algorism/tree/main/programers/%EA%B3%BC%EC%9D%BC%20%EC%9E%A5%EC%88%98