[LeetCode] 1710. Maximum Units on a Truck 파이썬 easy 정렬

1710. Maximum Units on a Truck

문제 해석:

2차원 배열에는 박스의 개수와 박스안에 들어있는 유닛의 개수가 저장되어있다.
그리고 Maximum 값이 주어지는데, 이것은 트럭에 올릴 수 있는 최대 박스 개수이다.
박스를 최대한 트럭에 실었을때, 최대의 유닛 개수를 구하자.

문제 풀이:

1. 트럭에 가장 많이 실어올리기 위해선 유닛이 가장 많은 박스를 올리는 것이 유리하다.
2. 정렬을 이용해 유닛 순으로, 오름차순으로 정렬한다.
3. 트럭에 실은 박스의 개수가 TruckSize가 넘기 전까지 박스 X 유닛의 값을 더해준다.
4. 박스의 개수가 TruckSize를 넘겼을때, 값을 더해주지 않고 실을 수 있는 만큼의 마지막 박스만 계산한다.

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

• numberOfBoxesi is the number of boxes of type i.
• numberOfUnitsPerBoxi is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

 

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4 Output: 8 Explanation: There are: - 1 box of the first type that contains 3 units. - 2 boxes of the second type that contain 2 units each. - 3 boxes of the third type that contain 1 unit each. You can take all the boxes of the first and second types, and one box of the third type. The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10 Output: 91

 

Constraints:

• 1 <= boxTypes.length <= 1000
• 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
• 1 <= truckSize <= 106

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
    	# 박스 유닛으로 오름차순 정렬
        sBoxTypes = sorted(boxTypes, key = lambda x : -x[1])
        cnt = 0
        ans = 0
        for box, unit in sBoxTypes:
        	# 박스와 유닛을 곱하기 전에 개수 확인
            cnt += box
            if cnt > truckSize:
            	# 박스를 실은 개수가 초과했을때, 남은 공간만큼 유닛 계산하여 싣기
                ans += (truckSize - (cnt - box)) * unit
                break
            ans += box * unit
        return ans