[Hackerrank in C] Array Manipulation

문제

https://www.hackerrank.com/challenges/crush/problem?h_l=interview&isFullScreen=true&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

Array Manipulation | HackerRank

 

풀이

각각의 query 마다 array를 업데이트하는 방법은 O(queries_rows * n) 이 걸려 n이 커질수록 너무 오래걸리게 된다.

이 문제는 prefix sum을 사용한 문제로 우리가 필요한 것만 update해서 푸는 방법이다. 

 

즉 바뀌는 값만 track하면 된다는 의미다. (순서는 상관없으므로)

a = 1, b = 3, k = 10일때, arr[a-1]부터 arr[b-1]까지 +10, 나머지는 +0 (no change)이므로

arr[i] 가 현재의 sum일때 (모든 query를 반영한), arr[a-1] = +10, arr[b] = -10로 표시할 수 있다.

 

changes[10, 0 , 0, -10, 0...]이 된다

 

코드

long arrayManipulation(int n, int queries_rows, int queries_columns, int** queries) {
    // track only the change in changes[n] = change at n.
    int* changes = (int*)calloc(n, sizeof(int));
    
    for(int i=0; i<queries_rows; i++) {
       int a = queries[i][0];
       int b = queries[i][1];
       int k = queries[i][2];
       
       int L = a - 1;
       int R = b;
       
       changes[L] +=  k;
       if(R < n) changes[R] -= k; 
    }
    
    long max = LONG_MIN;
    long curr = 0;
    for(int i=0; i<n; i++) {
        curr += changes[i];
        max = (max < curr)? curr: max;
    }
    
    free(changes);
    return max;
}