LeetCode (C/C++) 2256. Minimum Average Difference

https://leetcode.com/problems/minimum-average-difference/description/

---

풀이

- 1차 풀이

   입력 받은 값에서 i번째 인덱스까지의 누적합을 저장 → sum 벡터

   인덱스를 순회하며 sum[i] / i - (sum[size] - sum[i]) / (size - i) 계산, 최솟값과 그 때의 i 값 갱신2차 풀이

 

걸린 시간을 줄여보고자 위의 풀이에서 sum 값을 저장할 때 cal 벡터에 sum[i] / i 값을 함께 저장

 

 

수의 범위가 10^5 까지라 자료형을 long long으로 해야 함을 주의

---

코드

// 85ms, 87MB
typedef long long ll;

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        ll minAverage = 100'000'000'000;
        int minIdx = 0;
        int size = nums.size();
        vector <ll> sum(size + 1);

        // 누적합 저장
        sum[1] = nums[0];
        for (int i = 2; i <= size; i++) 
            sum[i] = sum[i - 1] + nums[i - 1];

        for (int i = 1; i <= size; i++) {
            ll val;
            
            // divided by zero
            if (i == size)
                val =  abs(sum[i] / i - (sum[size] - sum[i]));
            else
                val = abs(sum[i] / i - (sum[size] - sum[i]) / (size - i));
            if (val < minAverage) {
                minAverage = val;
                minIdx = i - 1;
            }
        }
        return minIdx;
    }
};

 

 

2차 풀이

// 78ms, 93.3MB
typedef long long ll;

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        ll minAverage = 100'000'000'000;
        int minIdx = 0;
        int size = nums.size();
        vector <ll> sum(size + 1), cal(size + 1);

        // 누적합 &  현재까지의 계산값 저장
        sum[1] = cal[1]  = nums[0];
        for (int i = 2; i <= size; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
            cal[i] = sum[i] / i;
        }

        for (int i = 1; i <= size; i++) {
            ll val;
            
            // divided by zero
            if (i == size)
                val =  abs(cal[i] - (sum[size] - sum[i]));
            else
                val = abs(cal[i] - (sum[size] - sum[i]) / (size - i));
                
            if (val < minAverage) {
                minAverage = val;
                minIdx = i - 1;
            }
        }
        return minIdx;
    }
};