23.04.05. 풀었던 문제들

2439. Minimize Maximum of Array

첫 접근

 오름차순인 부분수열에 대해 그들의 평균값이 될 수 있고, 남는 것을 균등히 분배할 수 있다.

• 1 3 5라면 -> 3 3 3이 될 것.
• 1 3 6라면 -> 3 3 4가 될 것.
• 1 3 7라면 -> 3 4 4가 될 것.

 따라서 오름차순 부분수열을 찾고, [그 부분수열 합의 평균] + [나머지 존재 then 1 else 0]이 답일 것이라 생각했다.

 

 그러나 [6, 9, 3, 8, 14]와 subarr를 바꾼 결과가 [7, 8, 8, 8, 9]처럼 또 오름차순인 경우에는 문제가 발생하며, strictly increasing이 아니라 monotonic increasing인 경우도 포함해야 한다. 그래서 이 접근은 틀린 접근이다.

 

다음 접근

 전체 수열을 잘 조절해서 monotonic increasing으로 만드는 대신, monotonic decreasing으로 만들면 어떨까? arr[i+1]에 있는 것을 arr[i]로 1의 값을 당겨올 수 있다. 따라서 당길 수 있을 만큼 당겨 [최대한 차이가 적게 monotonic decreasing]으로 만든다고 생각하자. 이래도 결과는 같다.

 처음부터 어떤 index i까지 봤을 때, index 0부터 i까지 [최대한 차이가 적은 monotonic decreasing]으로 만드려면 각 element를 arr[0]부터 arr[i]까지 sum / (i+1) + [나머지 존재 then 1 else 0]로 만들면 된다.  arr[i+1]에 있는 것은 arr[i]로 값을 당겨올 수 있기 때문이다. 이후 모든 i에 대해 이를 계산한 후 max값이 답이 된다.

// Runtime 123 ms Beats 94.48%
// Memory 71.4 MB Beats 28.9%

typedef long long ll;

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        int len = nums.size();
        ll psum = nums[0];
        int answer = (int)psum;
        for(int i = 1; i < len; i++){
            psum += nums[i];
            answer = max(answer, (int)(psum / (i+1) + (psum % (i+1) == 0 ? 0 : 1)));
        }
        
        return answer;
    }
};

 

시간복잡도

 단 1번 순회하므로 O(n)이다.

 

공간복잡도

 별다른 공간을 사용하지 않으므로 O(1)이다.

 

후기

 어렵다. 직관으로 접근하는 게 어려운 아이디에이션 문제.