[python3] 2439. Minimize Maximum of Array

풀이 일자: 23.04.05

난이도: [Medium]

분류: [Array, Prefix Sum]

문제 내용

nums배열이 주어졌을 때 이는 n의 음수가 아닌 정수를 포함하고 있다. 이때 1~n-1의 인덱스를 골라 그 인덱스를 i번째라고 한다면  nums[i]는 1을 줄이고 nums[i-1]는 1을 증가시켜서 배열의 최댓값이 최소가 되도록 만드는 문제이다.

문제 해결 흐름

1. 최대한 Greedy하게 풀면 되지 않을까라는 생각을 해보았다. ( Fail to Solve)

→ 배열에서 가장 큰 값과 큰 값을 기준으로 왼쪽에 있는 값들중 가장 작은 값을 비슷하게 만들다보면 뭔가 평균에 수렴하지 않을까라는 생각에 기반하였다.

문제)
-1 +1
	
응용)
   -1 +1
-1 +1
---------
-1  0 +1

=> 위의 방식대로 연쇄적으로 이어진다고 치면 바로 왼쪽을 -1을 할 필요없이 왼쪽 중에 하나 골라서 -1을 하면 됨.

=> ans로 나올 수 있는 가장 최적의 값은 배열의 원소들의 평균과 0번째 원소 중 큰 것이 ans이 가질 수 있는 최솟값이다.

 

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:

        optMaxmin = max(ceil(sum(nums)/len(nums)), nums[0]);
        maxNum = max(nums);

        while(optMaxmin != maxNum):
            maxIdx = nums.index(maxNum);
            minNum = min(nums[:maxIdx]);
            minIdx = 0;
            
            for i in range(maxIdx, -1, -1):
                if nums[i] == minNum:
                    minIdx = i;
                    break;

            if nums[minIdx] + 2 <= maxNum:
                mid = (maxNum + nums[minIdx])/2;
                nums[minIdx] = ceil(mid);
                if minIdx == 0:
                    optMaxmin = max(optMaxmin, nums[0]);
                nums[maxIdx] = floor(mid);
            else:
                break;
            maxNum = max(nums);
            print(nums);
        
        return max(nums);

=> 20개정도에서 실패가 나오는데 생각해보면 이는 잘못된 코드로 뒤쪽의 가장 큰 수를 가장 작은 수에게만 나눠준 것으로 좀더 분산시켜서 나눠준다면 더 최적화가 될 것이다.

 

다른 해결 방식

1. 2시간 가량 풀이 끝에 결국 Solution을 확인했는데 Solution은 prefix sum으로 간단하게 해결하였다.

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        # Initialize answer and the prefix sum.
        answer = 0
        prefix_sum = 0
        
        # Iterate over nums, update prefix sum and answer.
        for i in range(len(nums)):
            prefix_sum += nums[i]
            answer = max(answer, math.ceil(prefix_sum / (i + 1)))

        return answer

Time Complexity:  O(N)

nums 배열 순회로 인한 nums의 길이만큼의 시간복잡도가 발생한다.

 

Space Complexity: O(1)

변수 이외의 다른 자료구조를 사용하지 않았기에 1의 공간복잡도를 가지게 된다.

 

 

=> 문제가 좋고 안좋고를 떠나서 항상 여러 방식을 시도해보고 쉬운 방법도 떠올려보자라는 교훈을 얻은 문제였다. 물론 카테고리가 binary Search에 DP도 포함되어 있어서 이를 활용해 풀이가 나올 줄 알았지만 .ㅎㅎ

 

 

문제 링크

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

Minimize Maximum of Array - LeetCode