C++에서 범위 합 쿼리가 적용된 배열로부터 초기 배열 찾기

문제 설명

이 문제에서는 크기가 N인 배열 res[]가 주어지며, 우리의 목표는 범위 합(range sum) 쿼리가 적용된 결과 배열로부터 원래의 초기 배열을 찾는 것입니다.

다시 말해, 어떤 시작 배열에 [s, e, val] 형태의 쿼리들을 순서대로 수행했을 때 최종적으로 배열 rel[]이 만들어진다면, 우리는 그 시작 배열, 즉 초기 배열을 구해야 합니다.

각 [s, e, val] 쿼리의 의미는 다음과 같습니다.

• s → 업데이트를 시작할 인덱스
• e → 업데이트를 끝낼 인덱스
• val → 배열의 s부터 e까지 모든 요소에 더해질 값

예제로 이해하기

입력 : rel[] = {7, 4, 8}
쿼리(Query)[][] = {{1, 2, 1},
{0, 1, 3}}
출력 : {4, 0, 7}

풀이 과정 −

initialArray = {4, 0, 7}; query = {1, 2, 1}; finalArray = {4, 1, 8}
initialArray = {4, 1, 8}; query = {0, 1, 3}; finalArray = {7, 4, 8}

초기 배열 {4, 0, 7}에 첫 번째 쿼리 {1, 2, 1}을 적용하면 인덱스 1~2의 요소에 1이 더해져 {4, 1, 8}이 됩니다. 여기에 두 번째 쿼리 {0, 1, 3}을 적용하면 인덱스 0~1의 요소에 3이 더해져 최종적으로 {7, 4, 8}이 완성됩니다.

해결 접근 방식

이 문제의 가장 단순한 해결 방법은 모든 쿼리를 순회하면서 각 쿼리의 영향을 하나씩 되돌리는 것입니다. 초기 배열을 찾아야 하므로, 쿼리 수행 시 사용했던 '더하기' 연산을 반대로 '빼기' 연산으로 처리하면 됩니다. 즉, 주어진 배열에서 각 쿼리의 [s, e] 범위에 해당하는 요소들에서 val을 차례로 빼주면 초기 배열을 얻을 수 있습니다.

이 방법의 시간 복잡도는 쿼리 개수를 Q라 할 때 O(N × Q)입니다. 쿼리마다 최대 N개의 요소를 갱신할 수 있기 때문입니다.

예제 프로그램

아래 프로그램은 이 해결 방법의 동작을 보여줍니다.

#include <iostream>
using namespace std;
void calcInitialArrayQueries(int arr[], int n, int query[][3], int q) {
    for (int i = 0; i < q; i++) {
        for (int j = query[i][0]; j <= query[i][1]; j++) {
            arr[j] = arr[j] - query[i][2];
        }
    }
    for (int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
}
int main() {
    int arr[] = { 5, 1, 8, 2, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int query[][3] = { {0, 2, -2}, {1, 4, 3}};
    int q = sizeof(query) / sizeof(query[0]);
    cout<<"Initial array : "; calcInitialArrayQueries(arr, n, query, q);
    return 0;
}

출력 결과

Initial array : 7 0 7 -1 6

실행 결과를 보면, 주어진 배열 {5, 1, 8, 2, 9}에 두 개의 쿼리 {{0, 2, -2}, {1, 4, 3}}를 역순으로 되돌려 값을 빼면 초기 배열 {7, 0, 7, -1, 6}이 얻어지는 것을 확인할 수 있습니다.