(Easy - Sliding Window) Leetcode - 643. Maximum Average Subarray I

숫자 배열이 주어지면 이 배열 안에서 만들 수 있는 연속된 부분 배열들 중 가장 큰 부분 배열의 평균값을 찾는 문제입니다.

만약 [1, 12, -4, -6] 배열이 있으면 부분 배열은 연속적으로 만들어져야 하므로 [1, 12]나 [12, -4, -6]과 같은 부분 배열은 가능하나 [1, -4]와 같이 떨어져 있는 원소들은 부분 배열로 만들 수 없습니다.

가장 큰 평균값을 찾는 것이므로 부분 배열의 원소의 수로 나누기 전 원소들의 합이 가장 큰 부분 배열을 찾으면 됩니다.

이때 문제에서 주어진 부분 배열의 길이는 k입니다.

즉, 부분 배열의 길이가 k인 배열의 원소들의 합이 가장 큰 경우를 찾으면 됩니다.

 

생각나는 가장 간단한 방법은 모든 부분 배열을 시도해보는 것입니다.

 

    double findMaxAverage(vector<int>& nums, int k) {
        double maxSum = INT_MIN;
        for (int i = 0; i + k <= nums.size(); ++i) {
            double sum = 0;
            for (int j = i; j < i + k; ++j){
                sum += nums[j];
            }
			
            if (maxSum < sum)
                maxSum = sum;
        }

        return maxSum / k;
    }

하지만 이렇게 할 경우 배열의 크기가 큰 경우 시간을 초과합니다. 

 

더 빠른 방법을 생각해보면 길이가 k인 연속적인 부분 배열을 찾는 것이므로 연속적인 4개의 원소들의 합 중 가장 큰 값을 찾으면 됩니다.

길이가 4인 박스를 옆으로 옮겨주면서 확인한다고 생각하면 되는데 옆으로 옮겨질때 가장 왼쪽에 있던 원소는 빠지고 새로운 원소가 추가됩니다.

이 방식으로 하면 시간복잡도 O(N)에 풀 수 있습니다.

    double findMaxAverage(vector<int>& nums, int k) {
        int maxSum = 0;
        // 맨 처음 index 0부터 3까지 길이가 k인 부분 배열의 합
        for (int i = 0; i < k; ++i) 
            maxSum += nums[i];

        int sum = maxSum;
        
        // 옆으로 옮기면서 비교
        for (int i = k; i < nums.size(); ++i) {
        	// 가장 왼쪽에 있던 값이 빠지고 새로운 값이 추가
            // ex) k가 4이고 i = 4일때, nums[i - k]로 index 0인 원소가 빠지고(-) 
            // 새로운 원소 nums[i]가 추가(+)됩니다. 
            sum = sum - nums[i - k] + nums[i];
            maxSum = std::max(maxSum, sum);
        }

        return static_cast<double>(maxSum) / k;
    }