Greedy HackerRank Algorithms in Java ‘Greedy Florist’ solution

Problem

A group of friends want to buy a bouquet of flowers. The florist wants to maximize his number of new customers and the money he makes. To do this, he decides he’ll multiply the price of each flower by the number of that customer’s previously purchased flowers plus 1. The first flower will be original price, (0 + 1) * original price , the next will be (1 + 1) * original price and so on. Given the size of the group of friends, the number of flowers they want to purchase and the original prices of the flowers, determine the minimum cost to purchase all of the flowers. For example, if there are k = 3 friends that want to buy n = 4 flowers that cost c = [1,2,3,4] each will buy one of the flowers priced [2,3,4] at the original price. Having each purchased x = 1 flower, the first flower in the list, c[0] , will now cost (current purchase + previous purchases) * c[0] = (1 + 1) * 1 = 2. The total cost will be 2 + 3 + 4 + 2 = 11.

Sample Input 0

3 3
2 5 6

Sample Output 0

13

Solution

문제의 설명이 조금 이상해서 헤맸다. 위에 ‘2 + 3 + 4 + 2 = 11’ 이라고 했는데 이 순서가 아니라, ‘2 + 2 + 3 + 4 = 11’이라고 생각하는 게 훨씬 이해가 잘 된다.

• 예제로 설명하면, k는 친구 수이고 3명이서 5개의 꽃을 나눠서 사야한다. 5 / 3 = 1 인데, 5 % 3 = 2 이므로 두명은 2개씩 꽃을 사야하고 1명만 1개의 꽃을 사면 된다. 이것을 루프를 돌며 friends[] 배열에 저장했다.
• 이렇게 저장하면, 배열 friends에는 인덱스 값이 앞일 수록 사야할 꽃의 수가 많아진다. (a[0] = a[1] = 2, a[2] = 1 이 된다.)
• 예제를 보면 꽃의 가격이 오름차순으로 들어오는 것 같지만, 문제 어디에도 오름차순으로만 제공한다는 말이 없어서 Arrays.sort를 사용해 꽃의 가격을 정렬했다.
• 그 이유는, 지불한 꽃의 가격이 최소가 되려면 가격이 낮은 꽃은 많이 사고 가격이 높은 꽃은 조금만 사면 된다. 따라서 많이 사야하는 순서대로 정렬한 것이다.
• friends 배열에는 사야하는 개수가 저장되어 있기 때문에 for문을 돌면서 샀으면 하나씩 줄여준다. – 연산을 먼저 한 이후는 처음 사면 (1 + 1)이 아니라 (0 + 1) 이므로!

Code

    // Complete the getMinimumCost function below.
    static int getMinimumCost(int k, int[] c) {
        int[] friends = new int[k];
        for(int i = 0; i < k; i++) friends[i] = c.length / k;
        for(int i = 0; i < c.length % k; i++) friends[i] += 1;
        
        Arrays.sort(c);
        int sum = 0, idx = 0;
        while(idx < c.length) {
            for(int j = 0; j < k; j++) {
                if(friends[j] > 0) sum += (--friends[j] + 1) * c[idx++];
            }
        }       
        return sum;
    }