C++로 배열의 모든 고유한 부분 배열 합의 총합 구하기

문제 개요

이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어집니다. 우리의 목표는 주어진 배열에서 서로 다른(고유한) 부분 배열 합들을 모두 찾아 그 총합을 구하는 것입니다. 여기서 부분 배열 합(subarray sum)이란 해당 부분 배열에 포함된 원소들을 모두 더한 값을 의미합니다.

예제로 문제 이해하기

입력 : arr[] = {1, 2, 4}
출력 : 23

설명 −

주어진 배열의 모든 부분 배열 :
(1), (2), (4), (1, 2), (2, 4), (1, 2, 4)
부분 배열 합의 총합 = 1 + 2 + 4 + (1+2) + (2+4) + (1+2+4) = 23

해결 접근 방법

이 문제를 해결하는 한 가지 방법은 먼저 모든 부분 배열의 합을 저장한 뒤, 이를 정렬하여 고유한 값들만 걸러내는 것입니다. 그 후 고유한 부분 배열 합들만 골라 더하면 최종 답을 얻을 수 있습니다.

알고리즘

1단계 − 모든 부분 배열의 합을 계산하여 벡터(vector)에 저장합니다.

2단계 − 벡터를 오름차순으로 정렬합니다.

3단계 − 인접한 값을 비교하여 중복되는 합은 0으로 만들고, 고유한 값만 남깁니다.

4단계 − 남은 값들을 모두 더해 결과를 출력합니다.

구현 예제

아래 프로그램은 위에서 설명한 해결 방법의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
   int i, j;
   long int sumArrayTill[n + 1] = { 0 };
   for (i = 0; i < n; i++)
      sumArrayTill[i + 1] = sumArrayTill[i] + arr[i];
   vector<long int> subArraySum;
   for (i = 1; i <= n; i++)
      for (j = i; j <= n; j++)
         subArraySum.push_back(sumArrayTill[j] - sumArrayTill[i - 1]);
   sort(subArraySum.begin(), subArraySum.end());
   for (i = 0; i < subArraySum.size() - 1; i++){
      if (subArraySum[i] == subArraySum[i + 1]) {
         j = i + 1;
         while (subArraySum[j] == subArraySum[i] && j < subArraySum.size()){
            subArraySum[j] = 0; j++;
         }
         subArraySum[i] = 0;
      }
   }
   long sum = 0;
   for (i = 0; i < subArraySum.size(); i++)
      sum += subArraySum[i];
   return sum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 9 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"모든 고유한 부분 배열 합의 총합은 "<<findSumOfSubArraySum(arr, n);
   return 0;
}

출력 결과

모든 고유한 부분 배열 합의 총합은 144

이 방식은 누적 합(prefix sum) 배열을 활용해 각 부분 배열의 합을 O(1) 시간에 구할 수 있다는 장점이 있으며, 전체 시간 복잡도는 정렬 과정 때문에 O(n² log n²) 수준이 됩니다.

해시 테이블을 활용한 또 다른 접근 방법

문제를 해결하는 또 다른 효율적인 방법은 해시 테이블(hash table)을 사용하는 것입니다. 모든 부분 배열의 합을 하나씩 구하면서 해시 맵(unordered_map)에 저장하고, 같은 합이 나타날 때마다 등장 횟수(count)를 1씩 증가시킵니다. 탐색이 끝난 후에는 등장 횟수가 정확히 1인 값, 즉 한 번만 나타난 고유한 부분 배열 합들만 골라 더하면 됩니다. 이 방법은 정렬이 필요 없으므로 평균적으로 O(n²)의 시간 복잡도로 해결할 수 있습니다.

구현 예제

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

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
   int sumSubArraySum = 0;
   unordered_map<int, int> sumSubArray;
   for (int i = 0; i < n; i++) {
      int sum = 0;
      for (int j = i; j < n; j++) {
         sum += arr[j];
         sumSubArray[sum]++;
      }
   }
   for (auto itr : sumSubArray)
      if (itr.second == 1)
         sumSubArraySum += itr.first;
   return sumSubArraySum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"모든 고유한 부분 배열 합의 총합은 "<<findSumOfSubArraySum(arr, n);
   return 0;
}

출력 결과

모든 고유한 부분 배열 합의 총합은 124

정리

두 가지 접근 방법 모두 모든 부분 배열의 합을 구한다는 기본 아이디어는 같지만, 정렬 기반 방식은 추가적인 O(n² log n²) 정렬 비용이 드는 반면, 해시 테이블 방식은 평균 O(n²)으로 더 효율적입니다. 따라서 입력 크기가 클 경우 해시 테이블을 활용한 방법이 일반적으로 더 좋은 선택입니다.