Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 부분 수열 너비의 합 알고리즘

문제 개요

정수 배열 A가 주어졌을 때, A로 만들 수 있는 모든 비어 있지 않은 부분 수열(non-empty subsequence)을 생각해 봅시다. 임의의 수열 S에 대해 '너비(width)'는 S에 속한 원소들의 최댓값과 최솟값의 차이로 정의됩니다. 즉, width(S) = max(S) − min(S)입니다.

우리가 구해야 할 것은 A의 모든 부분 수열 너비의 총합입니다. 이 값은 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환해야 합니다.

예를 들어 입력이 [3, 1, 2]라면 결과는 6입니다. 가능한 부분 수열은 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3]이며, 각각의 너비는 0, 0, 0, 1, 1, 2, 2입니다. 따라서 너비 값들을 모두 더하면 6이 됩니다.

핵심 아이디어: 각 원소의 기여도 계산

모든 부분 수열을 하나씩 직접 생성하면 지수 시간이 소요되어 비효율적입니다. 대신 각 원소가 최댓값 또는 최솟값으로 등장하는 횟수를 세면 문제를 훨씬 효율적으로 해결할 수 있습니다.

배열을 오름차순으로 정렬한 뒤 인덱스 i의 원소 a[i]를 살펴보겠습니다.

  • 최댓값으로 등장하는 경우: a[i] 앞쪽의 i개 원소 중 일부를 자유롭게 선택하면 a[i]는 해당 부분 수열의 최댓값이 됩니다. 이런 조합의 수는 2^i가지입니다.
  • 최솟값으로 등장하는 경우: 반대로 a[i] 뒤쪽의 (n−1−i)개 원소 중 일부를 선택하면 a[i]는 최솟값이 됩니다. 이런 조합의 수는 2^(n−1−i)가지입니다.

따라서 정답은 다음 식으로 표현할 수 있습니다.

answer = Σ a[i] × (2^i − 2^(n−1−i))

알고리즘 단계

모듈러 연산을 안전하게 처리하기 위해 add(), sub(), mul() 세 가지 헬퍼 함수를 먼저 정의합니다. 특히 뺄셈 함수는 결과가 음수가 되지 않도록 m을 더한 뒤 나머지를 구한다는 점이 중요합니다.

  1. 배열 a를 오름차순으로 정렬합니다.
  2. ans := 0, n := 배열의 크기, rcnt := 1로 초기화합니다.
  3. i를 0부터 n−1까지 반복하며 다음을 수행합니다.
    • x = mul(a[i], sub(rcnt, 1)) → a[i]가 최댓값일 때의 기여분
    • y = mul(a[n−1−i], sub(rcnt, 1)) → a[n−1−i]가 최솟값일 때의 기여분
    • ans = add(ans, sub(x, y))
    • rcnt를 두 배로 늘린 뒤 m으로 나머지를 취합니다.
  4. ans를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return ( (a % m) + (b % m) ) % m;
   }
   lli sub(lli a, lli b){
      return ( ( (a % m) - (b % m) ) + m ) % m;
   }
   lli mul(lli a, lli b){
      return ( (a % m) * (b % m) ) % m;
   }
   int sumSubseqWidths(vector<int>& a) {
      sort(a.begin(), a.end());
      int ans = 0;
      int n = a.size();
      lli rcnt = 1;
      for(int i = 0 ; i < n; i++){
         ans = add (ans, sub(mul(a[i] , sub(rcnt , 1)), mul(a[n-1-i], sub(rcnt,1))));
         rcnt <<=1;
         rcnt %= m;
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,1,2};
   cout << (ob.sumSubseqWidths(v));
}

입력

{3,1,2}

출력

6

시간 및 공간 복잡도

정렬에 O(n log n), 이후 한 번의 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 추가 배열 없이 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다. 덕분에 배열의 크기가 매우 크더라도 효율적으로 정답을 계산할 수 있습니다.