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

 

---

입출력 예

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합니다.

 

---

• 내 풀이

import java.util.*;
class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        
        List<Integer> list = new ArrayList<>();
        // score를 내림차순으로 변경하기 위한 list
        for(int i : score){
            list.add(i);
        }
        // 오름차순으로 정렬했다가 내림차순으로 변경해준다
        Collections.sort(list);
        Collections.reverse(list);

        // m개만큼 상자에 담아야 하기 때문에 그 이하로는 상자에 담을 수 없다
        while(list.size() >= m){
            // m개의 사과를 담고 최저 값을 구함
            int[] sum = new int[m];
            for(int i = 0; i < m; i++){
                sum[i] = list.get(i);
            }
            // 임의의 높은 값 , sum 배열에 담겨 있는 최저 값을 구해줌
            int min = k * m;
            for(int i = 0; i< sum.length; i++){
                min = Math.min(min , sum[i]);
            }
            
            // 상자에 담은 m 개 만큼 list에서 제거해줌
            int count = m;
            while(count>0){
                list.remove(0);
                count--;
            }
            answer += min * m;
        }

        return answer;
    }
}

11에서 15번 테스트에서 시간초과가 떴다

제한사항 7 ≤ score의 길이 ≤ 1,000,000 때문에 그런거 같은데 while문을 사용하지 말았어야 했나 싶다

 

• 재 풀이

import java.util.*;
class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        
        // 배열을 오름차순으로 정렬한다
        Arrays.sort(score);
        /**
         * 최댓값부터 m개씩 담으면서 내려온다
         * i = 배열은 0부터 시작이기 때문에 score.length-1
         * i가 m보다 크거나 같을 때까지 반복을 해야하는데 m개가 배열로 따지면 -1이 붙어야 해서 m-1이 된다
         * i는 m개 씩 줄어 들어야 한다
         */
        for (int i = score.length-1; m-1 <= i ; i -= m) {
            // m개를 담은 배열
            int[] sum = new int[m];
            // 배열에 0부터 담기 위한 변수
            int count = 0;
            // 최솟값을 구하기 위한 임의의 값
            int min = k * m;

            /**
             * j는 오름차순으로 정렬된 score의 끝에서 내려와야 하기 때문에 i 부터 시작
             * j가 j에서 m 만큼 뺀 값으로 반복을 시킨다 결국은 m 번 반복
             * 순차적으로 1씩 내려가며 m 번 반복
             */
            for (int j = i; j > i - m; j--) {
                sum[count++] = score[j];
            }
            for (int j = 0; j < sum.length; j++) {
                min = Math.min(min , sum[j]);
            }

            answer += min * m;
        }
        return answer;
    }
}

while문을 빼고 다른 분 풀이를 살짝 참고하여 다시 풀어보았다

 

 

 

• 다른 사람 풀이

import java.util.Arrays;


class Solution {
    public static int solution(int k, int m, int[] score) {
        Arrays.sort(score);
        int maxBoxLength = score.length / m;
        int[] box = new int[maxBoxLength];
        int idx = 0;
        int min = 10;
        for (int i = score.length - 1; i >= m-1; i -= m) {
            for (int j = i; j > i - m; j--) {
                min = Math.min(min, score[j]);
            }
            box[idx++] = min * m;
        }

        return Arrays.stream(box).sum();
    }
}