LeetCode 643: Maximum Average Subarray I

문제 설명

• 입력: 정수 배열 nums와 정수 k.
• 출력: 길이가 k인 연속된 부분 배열의 최대 평균.

---

접근 방법

1. 슬라이딩 윈도우를 사용하여 길이가 k인 연속된 부분 배열의 합을 효율적으로 계산.
2. 첫 번째 윈도우의 합을 계산한 후, 윈도우를 한 칸씩 오른쪽으로 이동하며 합을 업데이트.
3. 각 단계에서 최대 합을 추적하여 최종적으로 최대 평균을 반환.

---

코드

import 'dart:math'; // max 함수를 사용하기 위해 import

// 최대 평균 부분 배열을 계산하는 함수
double findMaxAverage(List<int> nums, int k) {
  // 초기 윈도우의 합 계산 (첫 번째 k개의 원소)
  int windowSum = 0;
  for (int i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  // 최대 합 변수 초기화
  int maxSum = windowSum;

  // 슬라이딩 윈도우: k부터 nums.length까지 반복
  for (int i = k; i < nums.length; i++) {
    // 윈도우 이동: 새로운 원소를 더하고 오래된 원소를 뺌
    windowSum = windowSum + nums[i] - nums[i - k];

    // 최대 합 업데이트
    maxSum = max(maxSum, windowSum);
  }

  // 최대 평균 반환
  return maxSum / k;
}

// 메인 함수: 테스트 케이스 실행
void main() {
  // 테스트 케이스 1
  List<int> nums1 = [1, 12, -5, -6, 50, 3];
  int k1 = 4;
  print(findMaxAverage(nums1, k1)); // 출력: 12.75

  // 테스트 케이스 2
  List<int> nums2 = [5, 5, 5, 5];
  int k2 = 2;
  print(findMaxAverage(nums2, k2)); // 출력: 5.0

  // 테스트 케이스 3
  List<int> nums3 = [0, 4, 0, 3, 2];
  int k3 = 1;
  print(findMaxAverage(nums3, k3)); // 출력: 4.0
}

---

코드 설명

초기 윈도우 계산

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

 

• 배열의 처음 k개의 요소를 합산하여 초기 윈도우 합을 계산합니다.
• 이 합은 windowSum 변수에 저장됩니다.

슬라이딩 윈도우 구현

for (int i = k; i < nums.length; i++) {
  windowSum = windowSum + nums[i] - nums[i - k];
  maxSum = max(maxSum, windowSum);
}

 

 

• 슬라이딩 윈도우를 오른쪽으로 한 칸 이동합니다:
  1. 새로운 원소 nums[i]를 더합니다.
  2. 오래된 원소 nums[i - k]를 뺍니다.
• 각 윈도우에서의 합을 계산하고, 최대 합을 업데이트합니다.

최대 평균 계산

return maxSum / k;

 

• 최종적으로 최대 합을 k로 나누어 최대 평균을 반환합니다.

시간 및 공간 복잡도

1. 시간 복잡도:
   • 초기 합 계산: O(k)
   • 슬라이딩 윈도우 업데이트: O(n - k) ≈ O(n)
   • 총 시간 복잡도: O(n)
2. 공간 복잡도:
   • 추가 공간 사용 없음: O(1)

---

실행 결과

테스트 케이스 1

입력:

nums = [1, 12, -5, -6, 50, 3], k = 4

 

출력:

12.75

설명:

• 부분 배열 [12, -5, -6, 50]의 평균이 12.75로 최대입니다.

 

테스트 케이스 2

 

입력:

nums = [5, 5, 5, 5], k = 2

 

출력:

5.0

 

설명:

• 모든 부분 배열의 평균이 동일합니다.

 

테스트 케이스 3

 

입력:

nums = [0, 4, 0, 3, 2], k = 1

 

출력:

4.0

 

설명:

• 요소 중 최대값인 4가 평균이 됩니다.