1. 문제
0 index부터 시작하는 길이 n 배열 nums와 정수 k가 주어진다.
인덱스 i를 중심으로 하고 반지름 k인 nums의 하위 배열에 대한 k-radius average는 i - k부터 i + k까지(포함한) 모든 요소 합의 평균이다.
만약 i의 전후로 k 미만의 요소가 있다면 k-radius average의 값은 -1이다.
길이 n의 avgs를 반환하는데, avgs[i]는 index i를 중심으로 한 하위 배열의 k-radius average이다.
x의 평균은 x의 합을 x로 정수 나누기를 한 값이다. 즉, 소수 부분은 소실된다.
예를 들어, 4개 요소인 2, 3, 1, 5의 평균은 11 / 4 = 2.75이며, 2로 잘린다.
문제가 주절주절 장황하지만 쉽게 말하자면 nums[i]에 대해서 i - k가 0 이상, i + k가 nums.Length 미만임을 만족한다면 avgs[i]는 i - k부터 i + k까지의 평균이고, 소수점은 버림 한 뒤 avgs를 리턴하면 된다.
조건을 만족하지 못한다면 avgs[i] 는 -1이다.
2. 풀이 과정
먼저 avgs를 선언하면서 -1로 초기화해 둔다. 조건을 만족하는 인덱스만 값을 채워 넣으면 되기 때문.
k * 2 + 1, 즉 지름이 nums안에 존재한다면 첫 합계를 sum에 저장하고 그 평균값을 avgs에 저장한다.
nums는 int지만 합계는 int가 저장할 수 있는 값을 넘어설 수 있기 때문에 sum은 8byte인 long형으로 선언한다.
첫 sum을 구했다면 그 이후로는 nums를 순회하며 sum을 재활용할 수 있다.
조건을 만족하는 nums[i]에 대해서 sum이 구해졌고 nums[i + 1]도 조건을 만족한다면 nums[i + 1]의 sum은 nums[i]의 sum에서 nums[i - k - 1]을 빼고 nums[i + k]를 더해준 것과 같다.
불필요한 예외문을 피하기 위해 조건을 만족하는 인덱스인 k + 1부터 nums.Length - k 미만까지 순회하며 avgs를 계산한 뒤 반환한다.
public class Solution {
public int[] GetAverages(int[] nums, int k) {
int[] avgs = Enumerable.Repeat(-1, nums.Length).ToArray();
long sum = 0;
int diameter = k * 2 + 1;
if(diameter <= nums.Length)
{
for(int i = 0; i < diameter; ++i)
{
sum += nums[i];
}
avgs[k] = (int)(sum / diameter);
}
for(int i = k + 1, length = nums.Length - k; i < length; ++i)
{
sum -= nums[i - k - 1];
sum += nums[i + k];
avgs[i] = (int)(sum / diameter);
}
return avgs;
}
}
'LeetCode 풀이노트' 카테고리의 다른 글
[C#] 1493. Longest Subarray of 1's After Deleting One Element (0) | 2023.07.05 |
---|---|
[C#] 137. Single Number II (0) | 2023.07.04 |
[C#] 1161. Maximum Level Sum of a Binary Tree (0) | 2023.06.15 |
[C#] 2352. Equal Row and Column Pairs (0) | 2023.06.13 |
[C#] 1351. Count Negative Numbers in a Sorted Matrix (0) | 2023.06.08 |