[해커랭크] Array Manipulation (C++)

문제 링크: www.hackerrank.com/challenges/crush/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

Array Manipulation | HackerRank

1. 주의할 점

- 각 쿼리를 입력 받을 때 마다 모든 배열에 값을 추가하지 않는다 -> TLE 발생

 

2. 구현

- 아이디어가 떠오르지 않아서 Discussion에 적혀 있는 다른 사람의 풀이를 참조하여 해결했다.

- 방법은 현재 배열의 값: 현재 배열의 값 + 이전 배열의 값으로 해결한다

- 쿼리의 첫 번째 요소: A, 쿼리의 두 번째 요소: B, 쿼리의 세 번째 요소: Val이라고 가정한다

- A~B까지 Val만큼을 더해야 한다 -> 시작지점인 A에만 Val만큼 더한다

- Val만큼 더하는 범위 즉, B까지 알아야한다. 어떻게 표현해야 할까?

- Point: 이전의 원소값을 더한다 -> 합이 0이 되도록 B+1번째 원소에는 -Val만큼 미리 더한다

- 쿼리문을 입력 받을 때, Arr[A]+=Val을 수행하고 B+1번째 원소가 배열의 범위에 속한다면, Arr[B+1]-=Val을 수행한다

- 1~N까지의 배열을 탐색하며 최대값을 찾는다

long long arr[10000001];
// Complete the arrayManipulation function below.
long arrayManipulation(int n, vector<vector<int>> queries) {
    for(int i=0;i<queries.size();i++){
        int a = queries[i][0];
        int b = queries[i][1];
        int val = queries[i][2];
        arr[a]+=val;
        if(b+1<=n) arr[b+1]-=val;
    }
    
    long long result=0;
    for(int i=1;i<=n;i++){
        arr[i]+=arr[i-1];
        result = max(result,arr[i]);
    }
    return result;
}