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

문제

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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합니다.

---

흐름

1. 전체 사과 리스트인 LinkedList와 한 사과박스로 칭할 ArrayList를 선언한다.
2. 사과 리스트를 최상품 순으로 정렬한다.
3. 한 사과박스(ArrayList)에 사과를 m개씩 담는다. 이 때, 전체 사과 리스트가 최상품 순으로 정렬되어 있기 때문에 최대 이익이 날 수 있도록 담긴다.
4. 담았던 사과박스가 다 찼을 경우, 사과 상자의 가격을 계산한다.
5. 박스에 담은 사과 개수(m)만큼 전체 사과 리스트(LinkedList)에서 제거한다.
6. 사과를 다시 담기 위해 사과박스(ArrayList)를 비워준다.
7. 전체 사과 리스트(LinkedList)가 한 사과박스 당 담을 수 있는 사과 개수(m) 이상 남아 있을 동안 만큼 반복한다.

결과

public class ex02 {
	static int solution(int k, int m, int[] score) {
        int answer = 0;
        int boxAmount = 0;    // 한 사과박스 당 가격
        List<Integer> appleList = new LinkedList<>(); // 전체 사과 리스트
        ArrayList<Integer> box = new ArrayList<>();   // 한 사과박스

        for (int s : score) {
            appleList.add(s);
        }

        Collections.sort(appleList, Collections.reverseOrder()); // 사과를 최상품 순으로 정렬

        while (appleList.size() >= m) {
            for (int i = 0; i < m; i++) {
                box.add(appleList.get(i));
            }
            
            if (box.size() == m) {
                // 내림차순으로 정렬된 리스트에서 순차적으로 넣었기 때문에, 
                // 맨 마지막 인덱스의 사과점수로 가격 계산
                boxAmount = box.get(box.size() - 1) * m;
                answer += boxAmount;

                for (int j = 0; j < m; j++) {
                    appleList.remove(0);
                }
            }
            
            box.clear();
        }
        return answer;
    }


    public static void main(String[] args) {
//        int k = 3;
//        int m = 4;
//        int[] score = {1, 2, 3, 1, 2, 3, 1};
        int k = 4;
        int m = 3;
        int[] score = {4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2};
        solution(k, m, score);
    }
}

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