[연습문제] 과일 장수

https://school.programmers.co.kr/learn/courses/30/lessons/135808

프로그래머스

---

문제 설명
과일 장수가 사과 상자를 포장하고 있습니다.

사과는 상태에 따라 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 해주세요.

---

입출력 예

k	m	score	result
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

---

입출력 예 설명
입출력 예 #1

• 문제의 예시와 같습니다.

입출력 예 #2

• 다음과 같이 사과 상자를 포장하여 모두 팔면 최대 이익을 낼 수 있습니다.

사과 상자	가격
[1, 1, 2]	1 x 3 = 3
[2, 2, 2]	2 x 3 = 6
[4, 4, 4]	4 x 3 = 12
[4, 4, 4]	4 x 3 = 12

• 따라서 (1 x 3 x 1) + (2 x 3 x 1) + (4 x 3 x 2) = 33을 return합니다.

---

과일 장수가 상자에 사과를 m개 담아서 팔 때 얻을 수 있는 최대 이익을 구하는 문제입니다.

 

문제에서 중요한 키포인트가 있는데, 바로 다음 지문들입니다.

• 사과는 상자 단위로만 판매하며, 남는 사과는 버립니다.
• 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.

사과는 항상 상자 단위로 판매하기 때문에, 상자 안에는 비싼 사과들이 가장 많이 들어가야 합니다.

예를 들어 [4, 4, 4, 1, 1, 1]을 3개씩 상자로 구성한다고 가정했을 때, [4, 4, 1], [4, 1, 1]처럼 4를 분배하는 것보다는 [4, 4, 4], [1, 1, 1]처럼 한 쪽에 몰아주는 편이 더 판매 금액이 크다는 뜻이죠.

 

따라서 사과를 비싼 순서대로 정렬한 뒤, 이를 m개씩 자르는 편이 가장 큰 이득을 가져올 수 있습니다.

이 정보를 바탕으로 정답 코드를 작성해보겠습니다.

자바에서는 스택을, 파이썬에서는 리스트 슬라이싱을 사용합니다.

 

1. 자바

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        // 스택 관련 변수
        Stack<Integer> st = new Stack<Integer>();
        int minScore = 0;
        // 사과를 오름차순 정렬합니다.
        Arrays.sort(score);
        // 역순으로 탐색합니다.
        for (int i = score.length - 1; i >= 0; i--) {
            // 상자에 사과를 집어넣습니다.
            st.push(score[i]);
            // 스택의 크기가 m개 이상일 경우
            if (st.size() == m) {
                // 가장 마지막에 들어간 값이 해당 상자의 가장 작은 값
                minScore = st.pop();
                // 상자의 가격을 이익에 추가합니다.
                answer += (minScore * m);
                // (m - 1)개를 상자에서 제거합니다.
                for (int j = 0; j < m - 1; j++) {
                    st.pop();
                }
            }
        }
        return answer;
    }
}

 

2. 파이썬

def solution(k, m, score):
    # 이익을 저장하는 answer
    answer = 0
    # 사과를 비싼 순서대로 정렬합니다.
    score.sort(reverse = True)
    # 상자에 담을 수 있는 최대 개수만큼 자릅니다.
    for i in range(0, len(score), m):
        # 상자를 설정합니다.
        box = score[i:i+m]
        # 상자에 사과가 최대치만큼 담겼다면
        if len(box) == m:
            # 해당 상자를 팔며 이득을 냅니다.
            answer += (min(box) * m)
    # 이익을 반환합니다.
    return answer

 

상자 단위로만 팔 수 있기 때문에 팔 수 있는 최대 상자는 (사과의 개수) / m 개입니다.