[DAY 8] Greedy Florist

A group of friends wants 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 purchase) * c[0] = (1 + 1) * 1 = 2. The total cost will be 2 + 3 + 4 + 2 = 11.

 

Greedy Florist | HackerRank

 

풀이

function getMinimumCost(k, c) {
    let totalPrice = 0;
    if(k == c.length) {
        for(let i = 0; i < k; i++) {
            totalPrice += c[i];
        }
    } else {
        c.sort((a, b)=> a - b);
        let repurchase = 0;
        let currentPrice = 0; 
        let customer = 0;
        for(let i = (c.length - 1); i >= 0; i--) {
            currentPrice = (repurchase + 1) * c[i];
            totalPrice += currentPrice;
            customer++;
            if(customer % k == 0) repurchase++;
        }
    }
    return totalPrice;
}

1. 전체 가격이 들어갈 변수를 0으로 초기화해줌

2. 구매자 수와 사야할 꽃의 수가 같다면, 한 사람당 한 개씩 구매하면 됨. 따라서, for문을 이용해 totalPrice 변수에 배열 값을 다 더해줌

3. 사람 수보다 사야할 꽃이 많다면, 먼저 비싼 순서대로 정렬을 해줌(처음에 정렬을 안해서 일부 문제에서 Fail됨😅)

4. 재구매 횟수(repurchase), 현재 가격(currentPrice), 고객 수(customer)를 0으로 초기화해줌

5. 큰 가격일 수록 첫구매를 하는 것이 이득이므로, for 문을 역으로 돌면서 currentPrice을 repurchase와 현재값을 이용해 계산하고 totalPrice에 더해줌

6. 이때, 한 바퀴 돌때마다 customer값을 1씩 더해주면서 customer가 k의 배수가 될때마다 repurchase 값을 1씩 더해줌

7. totalPrice를 리턴함.

 

 

다른 사람의 풀이

function getMinimumCost (k, c) {

    // Create a 2D array holding purchase order for each friend
    let purchases = new Array(k).fill(0).map(x => [])

    // Sort flowers from most expensive to cheapest
    c.sort((a,b) => b-a)

    // Distribute purchases evenly between friends
    for (let i = 0, l = c.length; i < l; i++) purchases[i%k].push(c[i])

    // Calculate and return sum of all purchases
    return purchases.reduce( (total_cost, friend_total) => {
        return total_cost + friend_total.reduce( (total, cost, i) => {
            return total + (i + 1) * cost
        }, 0)
    }, 0)
}

친절하게도 주석으로 설명을 다 써줬네염

이중배열을 만들어서 [i%k]의 형태로 배열의 위치에 값을 각각 넣어줬군여

그리고 reduce를 이용해 서 전체 값에 현재값을 더해주고, 각 친구들의 전체값을 더해주었다!

심지어 그걸 한줄로 줄임...

const getMinimumCost = (k, c) => c.sort((a,b) => b-a).reduce((a,v,i) => a + (Math.floor(i/k) + 1) * v, 0)