643. Maximum Average Subarray I

📌 문제 링크 :

https://leetcode.com/problems/maximum-average-subarray-i

 

✅ 내 풀이(Success) :

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double sum = 0;
        int n = nums.length;

        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        double average = sum / k;
        for (int i = k; i < n; i++) {
            sum += (nums[i] - nums[i-k]);
            average = Math.max(average, sum / k);
        }
        return average;
    }
}

 

🔨 리팩토링 :

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double maximum = 0;
        int n = nums.length;

        for (int i = 0; i < k; i++) {
            maximum += nums[i];
        }
        double checkNum = maximum;
        for (int i = k; i < n; i++) {
            checkNum += (nums[i] - nums[i-k]);
            maximum = Math.max(maximum, checkNum);
        }
        return maximum / k;
    }
}

리팩토링 전과 후의 실행속도의 차이가 없다...

 

🧐 리뷰 :

초기 윈도우의 값을 구하고 for 반복문을 순회하면서 윈도우의 양 끝점의 값을 갱신하면서 최대 평균 부분배열을 구하는 간단한 문제였다.

문제를 해결하고 자바로 작성된 풀이는 좋아요를 많이 받은 풀이는 없어서 파이썬으로 작성된 풀이들을 보면서 내 코드와 비교했다.

한 풀이에서는 합계의 최댓값을 구하고 결괏값을 리턴하기 전에 딱 한 번 평균값을 구하는 풀이를 보았다.

당연하게도 분모가 고정된 값이라는 가정하에 분자가 최댓값인 경우를 찾으면 그때가 평균의 최댓값이므로 평균을 반복문을 순회하면서 매번 구할 필요는 없던 것 같다.

평균을 딱 한 번만 구하도록 코드를 리팩토링하고 제출했더니 시간복잡도는 달라지지 않았지만, 내심 연산의 횟수가 줄었으니 실행 시간의 차이가 있을 것이라고 기대했지만, 실행 시간 측면에서는 차이가 없었다.