LeetCode 643. Maximum Average Subarray I

 

 

 

 

초기 접근 방법

❗️처음에 생각한 방향

처음부터 해당 알고리즘을 공부할 목적으로 Sliding Window가 뭔지 검색하고 풀음

 

 

 

 

최종 접근

 

✅ 고정된 크기 k만큼의 avg를 먼저 구하고 해당 avg와 sliding 해서 구할 새로운 avg와 비교

 

 

✅ Sliding 한다는 것 :

window에 포함될 새로운 배열만큼 더하고,

window에서 빠질 가장 작은 배열만큼 뺀다.

 

for문 안에서 주어진 변수로 어떻게 한 번에 다 표시할 수 있을까 고민했고,

주어진 k와 i를 이용해 모두 표현 가능 >> [i]번째는 더하고, [i-k] 번째는 빼지는 구조

 

 

 

구현

Runtime : 129ms

Beats 89.49% of users with C

double findMaxAverage(int* nums, int numsSize, int k){
    double sum =0, avg;
    int i;

    for(int i=0; i<k; i++){
        sum += nums[i];
    }
    avg = sum/k;

    for(int i = k; i<numsSize; i++){
        sum -= nums[i-k];
        sum += nums[i];
        if(sum/k > avg) avg = sum/k;
    }

    return avg;
}

 

 

 

 

 

Take aways

✅ Sliding Windows 알고리즘

고정된 크기의 배열을 그대로 움직이는 개념으로 Two pointers과 유사하지만

그 크기가 고정되어 있다는 점에서 two pointers와 다름