I. 과일장수 문제

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

1. 문제 설명

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.

• 한 상자에 사과를 m개씩 담아 포장합니다.
• 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.

과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

• (최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8

사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

2. 제한 사항

• 3 ≤ k ≤ 9
• 3 ≤ m ≤ 10
• 7 ≤ score의 길이 ≤ 1,000,000
• 1 ≤ score[i] ≤ k

3. 풀이

과일 장수가 최대로 이익을 얻기 위해선 상대적으로 높은 가치를 지닌 사과들을 같은 박스에 담고, 상대적으로 낮은 가치를 지닌 사과들을 같은 박스에 담아야한다. 왜냐하면 낮은 가치를 지닌 사과들과 높은 가치를 지닌 사과들이 섞일 경우, 높은 가치를 지닌 사과의 가격은 낮은 가치를 지닌 사과와 동일하게 취급되기 때문이다.

결론적으로, 다음과 같이 진행했다.
1. 사과의 score를 입력받는다.
2. score[]를 내림차순으로 정렬한다.
3. m(한 상자에 들어가는 사과의 수)에 따라 score[]를 나눈다.
4. 나눠진 사과들 중 가장 낮은 점수에 m을 곱하고, 그 총합을 리턴한다.

4. 소스 코드

4-1) FruitVendor.java

public class FruitVender {

    public static void main(String[] args) {
        int result = 0;
        Scanner scanner = new Scanner(System.in);
        int m = 0;          // 한 상자에 들어갈 사과의 갯수
        int amount = 0;     // 포장할 사과의 갯수
        int k = 0;          // 사과 점수의 최댓값
        int[] scores = null; // 사과 점수 array
		
        // User Input
        while( m < 3 || m > 10){
            System.out.print("한 상자에 들어갈 사과의 수를 입력하시오.(3~10) > ");
            m = scanner.nextInt();
            scanner.nextLine();		// scanner buffer 초기화
        }
        while (amount < 7 || amount > 1000000){
            System.out.print("포장할 사과의 갯수를 입력하시오.(7~1000000) > ");
            amount = scanner.nextInt();
            scanner.nextLine();		// scanner buffer 초기화
            scores = new int[amount];
        }
        while (k<1 || k>9){
            System.out.print("사과 점수의 최댓값을 입력하시오(3~9). > ");
            k = scanner.nextInt();
            scanner.nextLine();		// scanner buffer 초기화
        }
        for (int i = 0; i < amount; i++){
            int score = 0;
            while (score <= 0 || score > k){
                System.out.printf("%d번째 사과의 점수를 입력하시오.(1~%d) > ", i+1, k);
                score = scanner.nextInt();
                scanner.nextLine();	// scanner buffer 초기화
                scores[i] = score;
            }
        }
        // 정렬을 위해 Class SortedArray 생성
        SortedArray sortedScores = new SortedArray(scores, amount);
        // score[i]를 삽입 정렬(내림차순)
        sortedScores.InsertionSortD();

        for (int i = 0; i < amount/m; i++){
            int worstApple = 10;	// 사과의 최고 점수는 7이므로, 10으로 초기화
            // 사과 박스 가격 선정(worstApple * m)
            for (int j = 0; j < m; j++){
                if (worstApple > sortedScores.array[m*i+j]){
           			// 상자에 담긴 사과 수 * 담긴 사과 중 최저 점수
                    worstApple = sortedScores.array[m*i+j];
                }
            }
            result = result + worstApple * m;
        }
        System.out.printf("Result: %d\n", result);
    }

4-2) SortedArray.java

package programmers.fruit_vender;

public class SortedArray {
    // field
    int[] array = null;
    int size;
    String type = null;

    // constructor
    public SortedArray(int[] passedArray, int passedSize){
        array = passedArray;
        size = passedSize;
    }
    // tools
    void Swap(int tmp1, int tmp2){
        int tmp = array[tmp1];
        array[tmp1] = array[tmp2];
        array[tmp2] = tmp;
    }
    
	// Algorithms
    public void SelectionSortA(){	
        for (int i = 0; i<size ; i++){
            int min = i;
            // 현재 자리부터 가장 작은 숫자 찾음
            for (int j = i+1; j<size; j++){
                if(array[min] >= array[j]){
                    min = j;
                }
            }
            // 가장 작은 숫자와 현재 자리 바꿈
            if (i != min){
                Swap(i, min);
            }
        }
        type = "SelectionSorted_Ascending";
    }
    public void SelectionSortD(){
        long start = System.currentTimeMillis();
        for (int i = 0; i<size ; i++){
            int max = i;
            for (int j = i+1; j<size; j++){
                if(array[max] <= array[j]){
                    max = j;
                }
            }
            if (i != max){
                Swap(i, max);
            }
        }
        type = "SelectionSorted_Descending";
        long end = System.currentTimeMillis();
        System.out.println(type + " 실행 시간 : " + (end-start));
    }
}