2090. K Radius Subarray Averages

https://leetcode.com/problems/k-radius-subarray-averages/description/

문제

정답

1. 처음 풀이

class Solution {
    public int[] getAverages(int[] nums, int k) {
        if(k == 0) {
            return nums;
        }
        int[] answer = new int[nums.length];

        for(int i = 0; i < nums.length; i++) {
            answer[i] = -1;
        }

        long sum = 0; // 오버플로우 방지 
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(i - (k * 2) < 0) {
                continue;
            }
            answer[i - k] = (int) (sum/(k*2+1));
            
            // 한 칸 이동 
            sum-=nums[i-(2*k)];
        }
        return answer;
    }
}

• 문제의 핵심 : 슬라이딩 윈도우를 옮길 때 마다 for문을 돌면서 합산을 다시 하는게 아니라 (이 경우 O(N^2)의 시간복잡도),
  합을 O(N)으로 할 수 있도록 코드를 짜는 것
  • 이를 위해 for 루프를 돌 때, 합을 누적시켜가며 계산 (O(N))
• 어차피 우린 sliding window가 가능한 곳부터 보면 되므로, if (i - (k*2) <0)이면 continue,
  슬라이딩 윈도우가 가능한 지점부터 평균을 구해서 정답 배열에 저장해주고, lt를 뺴줘서 한칸을 이동시킴
  -> 다음 루프에서 rt가 1증가하면서 자연스레 슬라이딩 윈도우가 이동
• 즉, 슬라이딩 윈도우가 불가능한 범위에선 배열을 -1로 놔두고, 슬라이딩 윈도우가 가능한 범위만 평균을 구해서 배열의 값을 갱신해주면 됨
  
• 해당 예시에선 rt의 index가 6,7,8일 때만 슬라이딩 윈도우가 가능
• 가능하다면, answer[i - k]의 값을 sum/(2*k+1)으로 갱신
• rt가 끝까지 가면 배열이 끝난거니까 끝내면, 뒷부분은 자연스레 갱신이 안되므로 -1로 고정
• 문제에서 입력 nums[i]는 최대 10^5이고, 길이는 최대 10^5까지 갈 수 있어.sum이 int 범위를 넘을 수 있다.
  → 오버플로우 발생 위험으로 sum을 long타입으로 지정

=> 근데 이렇게 어렵게 생각할 필요가 없었다! 그냥 슬라이딩 윈도우의 초기 합을 미리 구한 뒤, 그걸로 lt와 rt를 이용해 조작해주면 좀 더 간단함

2. 다른 풀이 (초기합 + 슬라이딩 윈도우 이용)

class Solution {
    public int[] getAverages(int[] nums, int k) {
        int[] answer = new int[nums.length];

        for(int i = 0; i < nums.length; i++) {
            answer[i] = -1;
        }

        if(2 * k + 1 > nums.length) { // 2 * k + 1, 즉 윈도우 사이즈가 배열의 길이보다 크다면, -1인 배열 반환
            return answer;
        } 
        if(k == 0) { // 0이라면 그냥 첫 배열 반환해주면 됨
            return nums;
        }


        long sum = 0; // 오버플로우 방지
        int windowSize = 2 * k + 1;
        for(int i = 0; i < windowSize; i++) {
            sum += nums[i];
        }
        answer[k] = (int) (sum / windowSize); // 첫 평균 저장

        // 첫 윈도우 rt + 1부터 시작
        for(int i = windowSize; i < nums.length; i++) {
            sum += nums[i]; // 한칸을 옮긴만큼 더해줌
            sum -= nums[i-windowSize]; // 한칸을 옮겼으니까, lt만큼을 빼줌
            answer[i - k] = (int) (sum / windowSize);
        }

        return answer;
	}
}

3. 다른 풀이 (prefix sum 배열 이용)

• 기존 풀이1이 누적합을 이용하되, 배열을 따로 안두고 즉석에서 구하는 방식 사용
  -> 공간복잡도 O(1)으로 더 좋은 풀이
• 하지만, prefix sum 배열을 이용해서도 풀어보자!

class Solution {
    public int[] getAverages(int[] nums, int k) {
        long[] prefixSum = new long[nums.length];
        prefixSum[0] = nums[0];
        for(int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i-1] + nums[i];
        }

        int answer[] = new int[nums.length];
        Arrays.fill(answer, -1); // 굳이 for문 돌 필요 X

        if(2 * k + 1 > nums.length) {
           return answer;
        }

        int lt = 0;
        long sum = 0;
        answer[k] = (int) (prefixSum[2 * k] / (2*k+1));

        for(int rt = 2 * k + 1; rt < nums.length; rt++) {
           sum = prefixSum[rt] - prefixSum[lt];
           lt++;
           answer[rt - k] = (int) (sum / (2*k+1));
        }

        return answer;
  }
}