Leetcode - 1710. Maximum Units on a Truck

문제

[박스갯수, 박스에 들어가는 유닛 갯수]의 배열이 주어지고, 트럭에 적재할수 있는 최대 박스갯수 (truckSize)가 주어질때, 배열에서 아무 박스나 선택이 가능할때, 유닛갯수가 최대가 되는 값은?

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8

해결

전형적인 greedy문제, 내림차순 정렬한뒤 가장 큰값부터 저장.

int cmp(const void *a, const void *b)
{
    int *aval = *(int **)a;
    int *bval = *(int **)b;
    return bval[1] - aval[1];
}

int maximumUnits(int** boxTypes, int boxTypesSize, int* boxTypesColSize, int truckSize){
    int ret = 0;
    qsort(boxTypes, boxTypesSize, sizeof(int*), cmp);
    for (int i = 0; i < boxTypesSize; i++) {
        if (boxTypes[i][0] <= truckSize) {
            ret += (boxTypes[i][0] * boxTypes[i][1]);
            truckSize -= boxTypes[i][0];
        } else {
            ret += truckSize * boxTypes[i][1];
            break;
        }
    }
    return ret;
}