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

---

프로그래머스 Lv1 - 과일 장수 문제

프로그래머스 레벨 1 과일 장수 문제를 풀이했다.

약간 그리디 알고리즘과 같이 최적해를 생각해보고 해당 최적해의 반례가 있을까 추론해보았지만 반례는 없을 것 같아 그대로 로직을 구현했다.

한 박스의 가격 = 가장 낮은 점수의 사과 * 박스 내 사과 개수

이라는 공식이 나오기 때문에 정렬하여 최대한 비슷한 점수의 사과끼리 박스에 묶어준다면 최고의 가격으로 팔 수 있다는 생각을 도출해내었다.

FruitSalesMan.java

package com.example.Programmers.Lv1;

import java.util.Arrays;

/**
 * 프로그래머스 Lv1 - 과일 장수 문제
 * 그리디 알고리즘 방식으로 풀이
 * 최적해 생각: 한 박스에 가장 낮은 점수의 사과를 기준으로 박스 가격를 구하기 때문에 최대한 낮은 점수는 낮은 점수끼리 모으면
 * 되겠다(정렬)
 */
public class FruitSalesMan {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int arrLen = score.length;
        int min = Integer.MAX_VALUE;
        int cnt = 1;
        // 오름차순 정렬
        Arrays.sort(score);

        for (int i = arrLen - 1; i >= 0; i--) {
            // 최소 점수 사과가 나오면 갱신
            if (min > score[i]) {
                min = score[i];
            }
            // 한 박스의 크기만큼 반복했다면 한 박스의 가격을 구해 정답에 더하기
            if (cnt == m) {
                answer += min * cnt;
                cnt = 0;
            }
            cnt++;
        }
        return answer;
    }
}

FruitSalesManTest.java

package com.example.Programmers.Lv1;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class FruitSalesManTest {
    @Test
    public void testFruitSalesMan() {
        FruitSalesMan f = new FruitSalesMan();

        int result1 = f.solution(3, 4, new int[] { 1, 2, 3, 1, 2, 3, 1 });
        int result2 = f.solution(4, 3, new int[] { 4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2 });

        assertEquals(8, result1);
        assertEquals(33, result2);
    }
}