[leetcode] 2439. Minimize Maximum of Array 파이썬 코드

https://leetcode.com/problems/minimize-maximum-of-array/

 

nums = [3, 7, 1, 6]

subproblem.

3만 바라보면, 3이 우리의 initial result이다. 3보다 더 작아질 수는 없기 때문이다.

 

이제 3과 7을 보자. operation을 한 번 하면 [4, 6]이 된다. 그 다음 [5, 5] 가 된다. 

[4, 6]의 최댓값은 6이고, [5, 5]의 최댓값은 5이다.

여기서 최댓값이 5보다 더 작아질 수 있을까?

operation을 한 번 더 하면 [6, 4]가 된다. 최댓값은 6이다. 즉, 5보다 더 작아질 수는 없다.

 

그럼 result 값을 5로 업데이트 하면 될까?

우리의 목표는 값을 evenly distribute 하는 것이다.

그렇기 때문에 평균값을 구해야 한다. [3, 7]의 평균은 5이다. 

result 값을 업데이트 하기 위해서는 3보다 클 때에만 업데이트 가능하다.

5가 3보다 크므로 result 값을 업데이트 할 수 있다.

따라서 result = max(result, 평균값)

 

한 가지 더, 만약 11 / 2 = 5.5 라면 6으로 올림해야 한다.

 

이 문제는 이걸 생각할 수 있으면 코드 짜는 건 아무런 문제가 없다.

문제는 이걸 생각할 수 있는지가 관건이다.

 

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        res = nums[0]
        for i in range(1, len(nums)): # 1, 2, 3
            nums[i] += nums[i-1]
            res = max(res, math.ceil(nums[i]/(i+1)))
        return res

 

생각해보니 구지 배열을 바꿀 필요가 없었다.

 

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        res = nums[0]
        currSum = nums[0]
        for i in range(1, len(nums)):
            currSum += nums[i]
            res = max(res, math.ceil(currSum/(i+1)))
        return res

 

배열의 원소를 바꾸지 않으면, 시간이 훨씬 단축된다.

 

---

참고

https://youtu.be/AeHMvcKuR0Y?si=hqoBxyXb9WNzBKOw