C++로 부분 배열의 비트 OR 결과 개수 구하기

문제 개요

음수가 아닌 정수로 이루어진 배열 A가 주어졌다고 가정해 봅시다. 배열의 모든 연속된 부분 배열 B = [A[i], A[i+1], ..., A[j]](단, i <= j)에 대해, B에 포함된 모든 원소의 비트 OR 연산 결과 A[i] | A[i+1] | ... | A[j]를 계산합니다. 우리가 구해야 하는 것은 이렇게 만들어질 수 있는 서로 다른 결과값의 개수입니다. 동일한 결과가 여러 번 나타나더라도 최종 답에는 한 번만 포함됩니다.

예를 들어 입력이 [1,1,2]라면, 만들 수 있는 부분 배열은 [1], [1], [2], [1,1], [1,2], [1,1,2]이고, 각각의 OR 결과는 1, 1, 2, 1, 3, 3입니다. 서로 다른 결과는 {1, 2, 3}의 세 가지이므로 정답은 3이 됩니다.

접근 방법

이 문제는 각 인덱스 i를 끝점으로 하는 부분 배열들의 OR 결과 집합을 관리하면 효율적으로 해결할 수 있습니다. 비트 OR 연산의 특성상, 한 인덱스에서 끝나는 부분 배열의 OR 결과 종류는 정수의 비트 수(약 30개)를 넘지 않으므로 집합의 크기가 작게 유지됩니다. 알고리즘은 다음과 같습니다.

• 두 개의 집합 ret(최종 결과 저장)과 curr2(이전 인덱스까지의 OR 결과 저장)를 생성합니다.

• i를 0부터 배열 크기까지 반복합니다.

  • 새 집합 curr1을 만들고 A[i]를 삽입합니다.

  • curr2의 각 원소 e에 대해 (e OR A[i])를 curr1에 삽입합니다.

  • curr1의 모든 원소를 ret에 삽입합니다.

  • curr2를 curr1로 갱신합니다.

• ret의 크기를 반환합니다.

예제 코드 (C++)

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int subarrayBitwiseORs(vector<int>& A) {
      unordered_set <int> ret;
      unordered_set <int> curr2;
      for(int i = 0; i < A.size(); i++){
         unordered_set <int> curr1;
         curr1.insert(A[i]);
         unordered_set<int>::iterator it = curr2.begin();
         while(it != curr2.end()){
            curr1.insert(*it | A[i]);
            it++;
         }
         it = curr1.begin();
         while(it != curr1.end()){
            ret.insert(*it);
            it++;
         }
         curr2 = curr1;
      }
      return ret.size();
   }
};
main(){
   vector<int> v = {1,1,2};
   Solution ob;
   cout << (ob.subarrayBitwiseORs(v));
}

입력

[1,1,2]

출력

3

복잡도 분석

시간 복잡도는 O(n × B)입니다. 여기서 n은 배열의 길이, B는 정수의 비트 수(약 30)로, 각 인덱스에서 끝나는 OR 결과 집합의 크기가 비트 수를 초과하지 않기 때문입니다. 공간 복잡도 역시 저장되는 집합의 크기에 비례하여 O(n × B)입니다.