[Java] 코딩 46 - 프로그래머스 기출 문제(JAVA) / 과일 장수 / Day 38

🍎 과일 장수

📘 문제 설명

과일 장수가 사과 상자를 포장하여 얻을 수 있는 최대 이익을 계산하는 문제입니다. 사과는 1점부터 $k$점까지 점수로 분류되며, 한 상자에 $m$개씩 담아 포장합니다. 상자의 가격은 상자에 담긴 사과 중 가장 낮은 점수 × $m$으로 결정됩니다. 과일 장수는 가능한 한 많은 사과를 팔아 최대 이익을 남기려 하며, 상자 단위로만 판매하고 남은 사과는 버립니다.

📌 제한조건

• 3 ≤ $k$ ≤ 9
• 3 ≤ $m$ ≤ 10
• 7 ≤ score의 길이 ≤ 1,000,000
• 1 ≤ score[i] ≤ $k$
• 이익이 발생하지 않는 경우에는 0을 반환합니다.

💡 개념 설명

• 알고리즘 핵심: 상자의 가격을 결정하는 것이 상자 내 '최저 점수'이므로, 높은 점수의 사과들을 최대한 같은 상자에 모아야 높은 가격을 유지할 수 있는 그리디(Greedy) 방식의 문제입니다.
• 로직 단계:
  1. 정렬: 사과 점수 배열(score)을 오름차순으로 정렬합니다.
  2. 역순 탐색: 가장 높은 점수부터 $m$개씩 묶기 위해 배열의 끝에서부터 $m$씩 건너뛰며 확인합니다.
  3. 최저 점수 선택: 뒤에서부터 $m$번째에 위치한 사과가 해당 상자의 최저 점수가 됩니다. (정렬되어 있기 때문)
  4. 이익 누적: (해당 인덱스의 점수 × $m$)을 answer에 더해줍니다.
  5. 반환: 모든 상자에 대한 계산이 끝나면 최종 합계를 반환합니다.

📎 입출력 예시

💻 프로그래머스 제출용 코드

import java.util.Arrays;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;

        // 1. 사과 점수를 오름차순으로 정렬
        Arrays.sort(score);

        // 2. 뒤에서부터 m개씩 묶어서 상자 만들기
        // 정렬된 배열의 끝에서 m번째 요소를 선택하면 그 상자의 최저 점수가 됨
        for (int i = score.length - m; i >= 0; i -= m) {
            answer += score[i] * m;
        }

        return answer;
    }
}

🖥️ IntelliJ 실행용 코드

import java.util.Arrays;

public class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;

        // 사과 점수 정렬
        Arrays.sort(score);

        // 뒤에서부터 m개씩 묶어 해당 상자의 가장 낮은 점수(score[i])를 찾아 계산
        for (int i = score.length - m; i >= 0; i -= m) {
            answer += score[i] * m;
        }

        return answer;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // 테스트 케이스 1
        int k1 = 3;
        int m1 = 4;
        int[] score1 = {1, 2, 3, 1, 2, 3, 1};
        System.out.println("결과 1: " + sol.solution(k1, m1, score1)); // 예상 결과: 8

        // 테스트 케이스 2
        int k2 = 4;
        int m2 = 3;
        int[] score2 = {4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2};
        System.out.println("결과 2: " + sol.solution(k2, m2, score2)); // 예상 결과: 33
    }
}

📎 결과