C++로 주어진 범위 내 요소들의 합으로 합계 배열 구성하기

문제 정의

정수로만 이루어진 배열 arr[ ]와 홀수인 값 sum이 주어졌을 때, 각 arr_2[i]가 arr[ ]의 이전 sum/2개 요소 + arr[i] + 다음 sum/2개 요소의 합이 되도록 합계 배열 arr_2[ ]를 구성하는 것이 목표입니다. 만약 sum이 1이라면 arr_2[i] = arr[i]가 됩니다.

예시

입력 1

arr[] = { 4, 1, 7, 5, 2, 9, 6, 2, 1 }, sum = 3

출력 1

주어진 범위 내 요소들의 합으로 합계 배열 구성 결과: 5 12 13 14 16 17 17 9 3

설명 1

합계 배열은 다음과 같이 구성됩니다:
arr_2[0] = arr[0] + arr[1] = 4 + 1 = 5
arr_2[1] = arr[0] + arr[1] + arr[2] = 4 + 1 + 7 = 12
arr_2[2] = arr[1] + arr[2] + arr[3] = 1 + 7 + 5 = 13
arr_2[3] = arr[2] + arr[3] + arr[4] = 7 + 5 + 2 = 14
arr_2[4] = arr[3] + arr[4] + arr[5] = 5 + 2 + 9 = 16
arr_2[5] = arr[4] + arr[5] + arr[6] = 2 + 9 + 6 = 17
arr_2[6] = arr[5] + arr[6] + arr[7] = 9 + 6 + 2 = 17
arr_2[7] = arr[6] + arr[7] + arr[8] = 6 + 2 + 1 = 9
arr_2[8] = arr[7] + arr[8] = 2 + 1 = 3

입력 2

arr[] = { 1, 2, 3, 4, 5 }, sum = 5

출력 2

주어진 범위 내 요소들의 합으로 합계 배열 구성 결과: 6 10 15 14 12

설명 2

합계 배열은 다음과 같이 구성됩니다:
arr_2[0] = arr[0] + arr[1] + arr[2] = 1 + 2 + 3 = 6
arr_2[1] = arr[0] + arr[1] + arr[2] + arr[3] = 1 + 2 + 3 + 4 = 10
arr_2[2] = arr[0] + arr[1] + arr[2] + arr[3] + arr[4] = 1 + 2 + 3 + 4 + 5 = 15
arr_2[3] = arr[1] + arr[2] + arr[3] + arr[4] = 2 + 3 + 4 + 5 = 14
arr_2[4] = arr[2] + arr[3] + arr[4] = 3 + 4 + 5 = 12

접근 방법

이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 활용해 해결할 수 있습니다. 이전 윈도우의 합계에 새로 들어오는 오른쪽 요소를 더하고, 윈도우에서 벗어나는 가장 왼쪽 요소를 빼면 매번 전체 합을 다시 계산하지 않고도 효율적으로 합계 배열을 구성할 수 있습니다.

정수 배열 arr[ ]와 값 sum을 입력으로 받습니다.
함수 sum_array(int arr[], int size, int sum)는 주어진 범위 내 요소들의 합으로 이루어진 합계 배열을 반환합니다.
초기 count 값을 0으로 설정합니다.
합계 배열을 arr_2[size]로 선언합니다.
temp = sum / 2 + 1로 설정합니다.
인덱스 0부터 temp까지의 요소들을 count에 더한 후, arr_2[0]을 count로 설정합니다.
합계 배열의 나머지 요소들은 for 루프를 통해 i=1부터 i<size까지 순회하며 계산합니다.
temp_1 = i − (sum / 2) − 1로 설정하고, temp_1이 0보다 크거나 같으면 count에서 arr[temp_1]을 뺍니다.
temp_2 = i + (sum / 2)로 설정하고, temp_2가 size보다 작으면 count에 arr[temp_2]를 더합니다.
arr_2[i] = count로 설정합니다.
for 루프가 종료되면 arr_2[ ]가 완성된 합계 배열이 됩니다.
for 루프를 사용하여 합계 배열 arr_2[ ]를 출력합니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;
void sum_array(int arr[], int size, int sum){
    int count = 0;
    int arr_2[size];
    int temp = sum / 2 + 1;
    for (int i = 0; i < temp; i++){
        count = count + arr[i];
    }
    arr_2[0] = count;
    for (int i = 1; i < size; i++){
        int temp_1 = i - (sum / 2) - 1;
        if (temp_1 >= 0){
            count = count - arr[temp_1];
        }
        int temp_2 = i + (sum / 2);
        if (temp_2 < size){
            count = count + arr[temp_2];
        }
        arr_2[i] = count;
    }
    cout<<"Construction of sum-array with sum of elements in given range are: ";
    for (int i = 0; i < size; i++){
        cout<< arr_2[i] << " ";
    }
}
int main(){
    int arr[] = { 4, 1, 7, 5, 2, 9, 6, 2, 1 };
    int sum = 3;
    int size = sizeof(arr) / sizeof(int);
    sum_array(arr, size, sum);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Construction of sum-array with sum of elements in given range are: 5 12 13 14 16 17 17 9 3

마무리

슬라이딩 윈도우 기법을 활용하면 각 위치마다 합을 처음부터 다시 계산하는 비효율적인 방식 대신, 한 번의 순회로 O(n) 시간 복잡도 안에 합계 배열을 구성할 수 있습니다. 윈도우에서 벗어나는 요소를 빼고 새로 들어오는 요소를 더하는 이 방식은 누적 합(prefix sum) 관련 문제에서도 널리 활용되는 핵심 기법이므로, 반드시 익혀두면 다양한 배열 문제 해결에 큰 도움이 됩니다.