[LeetCode] Maximum Average Subarray I

https://leetcode.com/problems/maximum-average-subarray-i/description/?envType=study-plan-v2&envId=leetcode-75

 

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

 

Example 2:
Input: nums = [5], k = 1
Output: 5.00000

 

Constraints:
n == nums.length
1 <= k <= n <= 105
-104 <= nums[i] <= 104

---

nums라는 숫자 배열과 숫자 k가 주어지고,

k개의 수를 배열 안에서 순서대로 더한 합을 k로 나눈 값 중 가장 큰 값을 구하는 문제.

결국 배열 안에서 i부터 i + k - 1까지 더했을때 최대값이 나오는 부분을 찾으면 된다.

 

단순히 풀려고만 하면 for문 두번 쓰면 그만이다.

const findMaxAverage = function(nums, k) {
    // nums라는 숫자 배열과 숫자 k가 주어짐
    // 소숫점 5자리까지 계산해야 함
    const numsLength = nums.length;
    let result = Infinity * -1;
    // 배열의 길이가 5이고 k가 3이라면 -> 0,1,2 / 1,2,3 / 2,3,4 / 3,4,5 로 4번만 돌면 됨
    for (let i=0; i < numsLength - k + 1; i++){
        let res = 0;
        for (let j=0; j < k; j++){
            res += nums[i+j];
        }
        result = res < result ? result : res;
    }
    
    return parseFloat(result/k.toFixed(5));
};

 

위 답은 테스트케이스 통과야 되지만 당연히 Time Limit Exceeded가 뜬다ㅋㅋ

 

순서대로 더한다는 문제의 특성을 이용해서...

1) 이전에 더해놓은 값을 저장해 두고

2) 그 다음 합은 이전 순서의 맨 앞 값을 빼고 이번 순서의 맨 뒷 값을 더하기만 하면 for문 하나를 아낄 수 있다.

 

const findMaxAverage = function(nums, k) {
    // nums라는 숫자 배열과 숫자 k가 주어짐
    // 소숫점 5자리까지 계산해야 함
    const numsLength = nums.length;
    let result = Infinity * -1;
    // 배열의 길이가 5이고 k가 3이라면 -> 0,1,2 / 1,2,3 / 2,3,4 / 3,4,5 로 4번만 돌면 됨
    // 배열 안에서 가장 큰 수가 포함되는 배열을 우선적으로 돌리게 한다면?
    let prev = 0;
    for (let x=0; x < k; x++){
        prev += nums[x];
    }
    // prev 초기값 = 0,1,2,3,..k-1 까지 더한 값
    for (let i=0; i < numsLength - k + 1; i++) {
        let res = prev;
        if (i > 0){
            // 이전 계산값을 보관하고 시작할 때는 새로운 거 하나만 더하게 한다면?
            res += nums[i+k-1];
            res -= nums[i-1];
            prev = res;
        }
    
        result = res < result ? result : res;
    }
    
    return parseFloat((result / k).toFixed(5));
};