LeetCode - 643 최대 평균 하위 배열1

 

643. 최대 평균 하위 배열1

 

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

 

문제

정수 배열 nums와 정수 k가 주어질 때, 길이가 k인 연속 부분 배열의 평균값 중 최대값을 찾는 함수를 작성하세요.
답을 소수점 다섯 번째 자리까지 반올림하여 반환합니다.

 

 

풀이1

1. nums.length 가 k 보다 클 때와 작을 때를 구분짓는다.

2. k 보다 작을 때 nums 의 요소 하나씩 더해서 length 만큼 나눈다.

3. 소수점 5번째 자리까지 올리기 위해 toStringAsFixed 함수를 사용한다.

4. k 보다 클 때 0번째 배열부터 k 길이까지 평균을 구해 resultList 에 삽입한다.

5. 위의 내용을 nums.length - k 길이까지 반복한다.

6. resultList 를 순서대로 정렬한다.

7. 정렬한 resultList 에서 제일 큰 마지막 원소를 반환한다.

double findMaxAverage(List<int> nums, int k) {
  double result = 0.0;
  int numsLength = nums.length;

  // k 가 nums 길이보다 크면 k 의 배월 원소들의 평균을 구하기
  if (numsLength <= k) {
    result = nums.reduce((pre, post) => pre + post) / numsLength;
    result = double.parse(result.toStringAsFixed(5)); // 소수점 5번째 자리 올림
  } else {
    int i = 0;
    List<double> resultList = []; // 평균 값 모음

    while (i <= numsLength - k) {
      // k 길이 만큼 배열 잘라서 더한 값
      int temp = 0;
      for (int j = i; j < k + i; j++) {
        temp += nums[j];
      }
      resultList.add(double.parse((temp / k).toStringAsFixed(5)));
      i++;
    }

    // 평균 값 모음 sorting 후 제일 큰 값 result 에 할당
    resultList.sort();
    result = resultList[resultList.length - 1];
  }
  return result;
}

 

풀이2 - 슬라이딩 윈도우 기법 사용

1. nums 배열을 원소의 값을 k 번째 까지 더한 값을 만든다.

2. maxSum 에 더한 값을 할당한다.

3. k 번째부터 nums 길이까지 반복문을 실행한다.

4. sum 에서 윈도우 앞 원소를 빼고 윈도우 뒷 원소를 더하여 값을 저장한다.

5. maxSum 과 sum 을 비교하여 최댓값을 저장한다.

6. maxSum / k 로 평균을 구한다.

// 슬라이딩 윈도우 기법 사용
double findMaxAverage(List<int> nums, int k) {
  int sum = 0;
  // nums 배열에서 k 번째 원소까지 더하기
  for (int i = 0; i < k; i++) {
    sum += nums[i];
  }

  // k 번째 원소의 합 저장
  int maxSum = sum;

  // k 번째부터 nums 길이까지
  // sum 에서 k 윈도우 앞 원소 빼고 k 윈도우에 포함된 뒷 원소 더하기
  for (int i = k; i < nums.length - 1; i++) {
    sum = sum - nums[i - k] + nums[k];
    maxSum = max(sum, maxSum); // maxSum 에 최댓값 저장
  }

  return maxSum / k;
}

 

이해가 안될 때는 그림으로 그리자!

 

제일 처음 for 문을 통해 나온 결과

 

두번째 for 문에서 첫번째 반복문

두번째 for 문에서 두번째 반복문

 

코드로 볼 땐 이해가 잘 안가지만 반복문을 하나씩 돌려서 대입해보면 이해가 간다.