[LeetCode] 1648. Sell Diminishing-Valued Colored Balls

문제 출처: https://leetcode.com/problems/sell-diminishing-valued-colored-balls/

Sell Diminishing-Valued Colored Balls - LeetCode

문제

다른 색 공이 들어 있는 inventory와 어떤 색의 공이든 orders개의 공을 원하는 소비자가 있다.

 

소비자는 색깔 공에 기묘하게 값을 매긴다. 각 색 공의 값은 inventory에 해당 색 공의 수이다. 예를 들어, 만약 6개의 노란 공을 갖고이 ㅆ다면, 소비자는 첫 번째 노란 공에 대해서 6을 지불할 것이다. 거래 이후, 5개의 노란 공이 남게 되고, 다음 노란 공은 5의 값어치가 매겨진다. (소비자가 공을 사면 살 수록 공의 값이 떨어진다.)

 

정수 배열 inventory가 주어지는데, inventory[i]는 i^th 색을 갖는 공의 수가 표현되어 있다. 또한 정수 orders는 소비자가 사길 원하는 공의 수이다. 어떤 순서로든 공을 팔 수 있다.

 

색 공을 orders만큼 팔 때 얻을 수 있는 가장 큰 값 을 반환하라. 답이 매우 클 수 있으므로, 10e9 + 1로 나눈 값을 반환하라.

예제

Input: inventory = [2,5], orders = 4
Output: 14

Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.

Input: inventory = [2,8,4,10,6], orders = 20
Output: 110

풀이

처음 시도한 방법은 Max Heap을 이용하여 매 순간 값이 가장 높은 공을 선택하는 방법이다.

// List를 Heqp 처럼 사용하는 heapPush(arr, val), heapPop(arr) 메소드가 존재한다고 가정할 때
var maxProfit = function(inventory, orders) {
    const heap = [];
    inventory.forEach(val => heapPush(heap, val));

    let ans = 0;
    for (let i = 0; i < orders; i++) {
        ans += heapPop(heap);
    }
    return ans;
}

// heapPush(arr, val)는 일반적인 힙 푸시와 동일하게 구현
var heapPush = function(arr, val) { ... }

// heapPop(arr)의 경우, 아래와 같이 구현
var heapPop = function(arr) {
    if (arr.length == 0) return 0;

    const ans = arr[0];
    arr[0] -= 1;
    if (arr[0] == 0) {
        arr[0] = arr[arr.length-1];
        arr.pop();
    }

    let cur = 0;
    let child = (2 * cur) + 1;

    while (child < arr.length) {
        if (child+1 < arr.length && arr[child] < arr[child+1]) { child += 1; }

        if (arr[cur] > arr[child]) { break; }
        [arr[cur], arr[child]] = [arr[child], arr[cur]];
        cur = child;
        child = (2 * cur) + 1;
    }

    return ans;
}

이 방법은 O((N+orders)logN) 이상의 시간복잡도를 갖는다. 이 시간복잡도는 leetcode측에서 제공하는 일부 테스트 케이스에서 시간 초과 에러를 내뿜는다. 이보다 더 짧은 시간에 문제를 해결할 수 있는 방법에 대해 생각해보아야 한다.

 

먼저, 매 순간 탐욕적인 방법으로 최대 값어치를 지닌 공을 판매해야 한다는 것은 자명한 사실이다.

 

이때, 해당 공이 어느 순간까지 가장 큰 값어치를 지닌 공인지 알 수 있다면, 그 공이 최대 값어치를 지닌 순간에 얻을 수 있는 총 값에 대해서 수학적으로 계산이 가능하다.

만약 inventory를 정렬한 배열이 다음과 같다면
sorted_inventory = [2, 5, 8, 10]

현재 가장 큰 값어치를 지닌 공의 값어치 = 10
그 다음으로 큰 값어치를 지닌 공의 값어치 = 8

현재 10 값어치의 공이 8 값어치가 될 때까지는 해당 공이 계속 선택되어짐
이때 얻을 수 있는 값어치는 10 + 9 = 19 이다.

이후, sorted_inventory = [2, 5, 8, 8]

이 경우 8 값어치의 공이 가장 크고, 그 다음으로는 5 값어치의 공이 가장 크다.
이 상황에서 또한 8 값어치의 공이 5 값어치가 되는 순간까지는 현재 8의 값어치를 지닌 공이 계속 선택되어 질 것이다.
이때 얻을 수 있는 값어치는 (8 + 7 + 6 + 5) * 2 = 52 가 된다.
주의!! 8의 값어치를 지닌 공이 2개 이기 때문에 2를 곱했다는 사실을 기억해야 한다.

현재까지 19 + 52 = 81 의 값어치를 팔았고, 2 + 8 = 10개의 공을 팔았다.

여기까지의 내용을 코드로 작성하면 다음과 같다.

var maxProfit = function (inventory, orders) {
    const map = new Map();
    inventory.forEach(val => {
        if (!map.has(val)) { map.set(val, 0); }
        map.set(val, map.get(val)+1);
    }); 

    const sortedInventory = Array.from(map.entries());
    sortedInventory.sort((a, b) => a[0] - b[0]);

    let ans = 0;
    let i = sortedInventory.length-1;
    let sameCount = sortedInventory[i][1];
    while (orders > 0) {
        const r = sortedInventory[i][0];
        const l = sortedInventory[i-1][0];

        // 이번 단계에서 한번에 팔 수 있는 묶음 계산
        const curCount = (r - l) * sameCount;

        ans += sameCount * (sigma(r) - sigma(l));
        orders -= curCount;

        sameCount += sortedInventory[i-1][1];
        i -= 1;
        ans %= (10e9 + 7);
    }

    return ans;
}

아직 orders에 대해서 제대로 고려하지 않았기 때문에, 불완전한 상태이다. 이제 orders에 대해서 조금 더 생각해보자.

sorted_inventory = [2, 5, 8, 8]라 하고 orders = 5 이라 가정

이전에 했던 것처럼 한번에 팔 수 있는 묶음을 계산하면, (8 - 5) * 2 = 6 인데, 이는 orders보다 크기 때문에 낱개로 파는 방법을 생각해야 한다.

5개의 공을 가장 높은 값어치로 선택을 하면 8, 8, 7, 7, 6 이 될 것이다. 이 값을 수학적으로 계산해보자.

현재 2개의 공이 가장 높은 값어치인 8을 지닌다. 이를 orders와 나눗셈, 나머지 연산을 하면 다음과 같은 결과를 얻을 수 있다.
- orders / 2 = 2 : 가장 높은 값어치를 지닌 모든 공을 1개씩 파는 행위를 2번 할 수 있음을 의미
- orders % 2 = 1 : 팔고 나서, 남은 나머지

최고 값어치의 공을 1개씩 2번 팔 수 있으므로, 8 + 8 + 7 + 7 의 값어치를 얻을 수 있다.
위 과정까지 팔고 나서도 1개의 공을 더 팔아야 하므로, 6 의 값어치를 추가적으로 얻을 수 있다.

즉, 5개의 공을 팔 때 8 + 8 + 7 + 7 + 6 = 36 의 값어치를 얻을 수 있다.

이 과정을 추가하여 코드를 작성하면 다음과 같다.

var maxProfit = function (inventory, orders) {
    const map = new Map();
    inventory.forEach(val => {
        if (!map.has(val)) { map.set(val, 0); }
        map.set(val, map.get(val)+1);
    }); 

    const sortedInventory = Array.from(map.entries());
    sortedInventory.sort((a, b) => a[0] - b[0]);

    let ans = 0;
       let i = sortedInventory.length-1;
    let sameCount = sortedInventory[i][1];
    while (orders > 0) {
        const r = sortedInventory[i][0];
        const l = i-1 < 0 ? 0 : sortedInventory[i-1][0];

        const curCount = (r - l) * sameCount;

        if (orders >= curCount) {
            ans += sameCount * (sigma(r) - sigma(l));
            orders -= curCount;
        } else {
            const takeAll = orders / sameCount;
            const takeRemain = orders % sameCount;

            ans += sameCount * (sigma(r) - sigma(r - takeAll));
            ans += takeRemain * (r - takeAll);

            orders -= (sameCount * takeAll) + takeRemain;
        }

        sameCount += i-1 < 0 ? 0 : sortedInventory[i-1][1];
        i -= 1;
        ans %= (10e9 + 7);
    }

    return ans;
}

Github: 1648.js

opwe37/Algorithm-Study