[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 해주세요.

 

---

입출력 예

---

코드 설명

첫 번째 코드

import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        List<Integer> list = new ArrayList<>();
        for(int s : score){
            list.add(s);
        }
        Collections.sort(list);
        for(int i = score.length -m; i >= 0; i-=m){
            answer += m*(list.get(i));
        }
        return answer;
    }
}

처음에 문제를 제대로 이해하지 못해 배열을 잘라서 이동을 해야하나 싶어 ArrayList를 이용하여 문제를 풀었습니다.
하지만 문제를 풀긴 했지만 시간이 너무 오래 걸린다는 단점이 있었습니다.

여기서 다시 생각을 해보니 배열 간의 이동이 있지도 않고 그냥 배열을 쓰면 된다는 것을 깨닫게 되었습니다. 처음에 알고리즘을 제대로 생각하지 않고 짜서 이러한 효율적이지 못한 코드를 짜게 된 것 같습니다.

 

그 후 저는 ArrayList를 배열로 바꿔 코드를 짜보았습니다. 그 결과 실행 시간이 많이 줄어든 것을 볼 수 있었습니다.

그러면 이제 배열로 짠 코드를 리뷰 해보겠습니다. 

 

두 번째 코드

Arrays.sort(score);

• 먼저 score배열을 오름차순으로 정렬해주었습니다.

for(int i = score.length -m; i >= 0; i-=m){
	...
}

• 그 후 score의 길이에서 m을 빼주었습니다. 그러면 m개수만큼 들어가는 박스를 만들 수 있습니다.
  여기서 score길이에서 m개수 만큼 뺀 값은 그 박스의 맨 앞 부분에 위치하므록, 그 수가 최솟값이 됩니다.
  다음 for문이 돌 때 마다 i에서 m만큼 빼주어 또 다른 박스를 만들어 줍니다.

answer += m*(score[i]);

• 이 때 socre[i]는 최솟값을 의미하므로 answer에 m과 score[i]를 곱하여 더해주도록 만들어 주었습니다. 

---

소스코드&결과

소스 코드

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 -m; i >= 0; i-=m){
            answer += m*(score[i]);
        }
        return answer;
    }
}

결과

---

이번 코딩테스트 문제를 풀면서 처음에 알고리즘을 잘 구상해야하는 중요성에 대해 깨닫게 되었습니다....

앞으로 문제를 풀기 전에 알고리즘을 신중하게 생각해보고 코딩을 하는 습관을 길러야 겠네요ㅠㅠ