Leetcode - 1652. Defuse the Bomb

문제

주어진 배열값과 k값으로 폭탄을 해체하는 코드를 생성해라. 코드를 생성하는 방법은, 각 자리수를 k개만큼 이전/이후 까지를 더한값으로 계산하면 된다. 아래 예시를 확인!
주의할 사항은 순환배열이라는 사실.

Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers. 
The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. 
Notice that the numbers wrap around.

Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4]. 
Notice that the numbers wrap around again. 
If k is negative, the sum is of the previous numbers.

https://leetcode.com/problems/defuse-the-bomb/

해결 O(n)

sliding window 구간합 문제, 매번 모든 구간을 더할필요없고 이전 sum에서 필요한 부분만 더하고 빼면 O(1) 에 합을 계산할 수 있다. 배열인덱싱은 항상 햇갈린다. 이번 문제는 인덱싱이 복잡해서 더 햇갈렸음.

배운것들.

• 순환(circular)하는 배열 -> 이런 단어가 나오면 항상 %으로 배열인덱싱을 한다.
• 시계방향 순환 인덱싱: [i % asize] / 반 시계방향 순환 인덱싱:?. (asize 배열크기)
• 이 문제의 경우 k가 음수/양수이건간에 시계방향 순환 인덱싱이기 때문에 [positino % asize] 으로 적절한 포지션을 계산한 뒤 % 크기 연산을 하면 된다.
  k < 0인경우 position 구하는 계산이 매우 햇갈렸다. 근데 생각해보면 시계방향으로 커지는것이기 때문에 그냥 적절한 position만 계산한다는 생각을 하면 될것같다. [((codeSize + k - 1) + i) % codeSize]

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* decrypt(int* code, int codeSize, int k, int* returnSize){
    int sum = 0;
    *returnSize = codeSize;
    int *ret = (int *)calloc(codeSize, sizeof(int));
    if (k == 0) {
        return ret;
    } else if (k > 0) {
        for (int i = 1; i < k + 1; i++)
            sum += code[i]; // no need to [i % codeSize]
        ret[0] = sum;

        for (int i = 1; i < codeSize; i++) {
            sum = sum - code[i] + code[(i + k) % codeSize];
            ret[i] = sum;
        }
    } else if (k < 0) {
        for (int i = codeSize - 1; i >= codeSize + k; i--)
            sum += code[i]; // no need to [i % codeSize]
        ret[0] = sum;
        
        for (int i = 1; i < codeSize; i++) {
            sum = sum - code[((codeSize + k - 1) + i) % codeSize] + code[(i-1) % codeSize];
            ret[i] = sum;
        }
    }
    return ret;
}