Skip to main content

[Java] 135808 과일 장수

📝 과일 장수

1. 문제 요약

  • 사과 점수: 1점(최하) ~ k점(최상)
  • 한 상자에 m개씩 담아 판매, 남는 사과는 버림
  • 상자 가격 = 상자 안 가장 낮은 점수 × m
  • 목표: 최대 이익을 얻도록 상자를 포장

2. 정답코드

  1. 사과 점수를 내림차순 정렬
  2. m개씩 묶어서 상자 만들기
  3. 상자 최소 점수 × m → 이익 누적
  4. 남는 사과는 버림
  5. 결과 = 가능한 많은 상자를 팔아 얻는 총 이익
import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        // 사고ㅏ몇 박스 ? score.length / m;
        // 각 사과 점수 계산 
        int len = score.length; // 사과박스 
        int box = len / m; // 점수 길이 
        int answer = 0; // 최대이익
        
        // 사과점수 내림차순
        // int[] → Integer[]로
        Integer[] arr = Arrays.stream(score).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Collections.reverseOrder());
        
        // m 개씩 묶어서 박스 가격 계산
        for (int i = 0; i < len / m; i++) {
            int start = i * m; // 아 이렇게 하면 되는구나
            int end = start + m - 1; // 박스 끝 인덱스
            int minScore = arr[end]; // 내림차순이라 제일 작은 값은 마지막 원소
            answer += minScore * m; 
        }
        
        return answer;
    }
}
  • arr를 내림차순 정렬 → 점수가 높은 사과부터 나열하기
  • box는 몇 개의 박스를 만들 수 있는지
  • for 문에서 i * m부터 i * m - m - 1까지가 한 박스
  • 그 박스에서 가장 작은 점수(arr[end]) * m → 이게 박스 가격
  • 모든 박스를 더한 값이 정답

3. 오답 / 어려웠던 점

1. m개씩 나누는 구간

  • 시작 인덱스 = i * m
  • 끝 인덱스 = i * m 에서 m - 1을 한 값

박스의 크기가 m이니까, 시작점에서 총 m개의 원소를 가져와야 한다.
시작이 start라면, 그 다음 인덱스는 start, start+1, start+2, … , start+(m-1) 까지가 한 박스이다.

arr는 내림차이니까, 구간 [start ~ end]안에서 가장 작은 값은 항상 arr[end]이다. 이렇게 하면 따로 최소값 찾을 필요 없이 바로 끝 원소를 쓰면 된다.

2. i는 배열 인덱스가 아니라 "박스 번호"이기 때문에, 반복 조건은 i < len / m

// m 개씩 묶어서 박스 가격 계산
for (int i = 0; i < len; i++) {
    int start = i * m; // 박스 시작 인덱스
    int end = start + m - 1; // 박스 끝 인덱스
    int minScore = arr[end]; // 내림차순이니까 제일 작은 값은 마지막 원소
    answer += minScore * m; 
}

image.png

배열 arr갸 있고, 배열을 m개씩 잘라서 “박스”를 만든다고 가정해 보자.

예를 들어서 len = 10, m = 3이면 박스는 len / m 개만 생긴다.
즉 10 / 3 = 3개의 박스만 만들 수 있다.

만약에 for (int i = 0; i < len; i++) 이라고 하면 i는 배열 인덱스처럼 0, 1, 2, 3, 4, ... 계속 올라간다.
하지만 우리가 원하는 것은 박스 번호이다. 즉 i는 박스 개수 단위로 반복해야 맞다. 따라서 조건은 i < len / m 이다.


Back to top