문제 정의
음수가 아닌 정수로 이루어진 배열과 하나의 정수 k가 주어졌을 때, 부분 집합에 속한 모든 원소를 비트 OR 연산한 결과가 정확히 k가 되는 최대 길이의 부분 집합을 찾는 것이 목표입니다.
예시
입력 배열 = [1, 4, 2], k = 3일 때 출력: [1, 2] 1과 2의 비트 OR 값은 3입니다. 길이가 2보다 큰 부분 집합은 만들 수 없습니다.
접근 방법
먼저 비트 OR 연산의 기본 성질을 살펴보겠습니다.
0 OR 0 = 0 1 OR 0 = 1 1 OR 1 = 1
k의 이진 표현에서 비트가 0인 자리에는, 결과 부분 집합에 포함되는 모든 원소의 해당 자리 비트도 반드시 0이어야 합니다.
반대로 k에서 비트가 1인 자리에는, 그 자리에 1을 가진 원소가 적어도 하나 이상 존재해야 합니다. 나머지 원소들은 해당 자리에 0이든 1이든 상관없습니다.
따라서 원본 배열을 순회하면서 각 원소를 부분 집합에 포함할지 판단할 때, k의 이진 표현에서 0인 자리에 해당 원소가 1을 가진 위치가 있는지 확인합니다. 그런 위치가 존재하면 해당 원소는 제외하고, 없다면 부분 집합에 포함시킵니다.
이 조건을 확인하는 방법은 간단합니다. k와 해당 원소의 비트 OR을 계산했을 때 결과가 k와 다르면, k에서 0인 자리에 원소가 1을 가진 경우이므로 제외해야 합니다. 반대로 OR 결과가 k와 같다면 현재 원소를 부분 집합에 포함합니다.
마지막 단계는 k에서 비트가 1인 자리에 대해, 부분 집합 안에 그 자리에 1을 가진 원소가 최소 한 개 이상 존재하는지 확인하는 것입니다.
부분 집합 전체의 비트 OR을 계산하여 그 값이 k와 같으면 최종 답입니다. 그렇지 않다면 조건을 만족하는 부분 집합은 존재하지 않습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void getSubSet(int *arr, int n, int k){
vector<int> v;
for (int i = 0; i < n; i++) {
if ((arr[i] | k) == k)
v.push_back(arr[i]);
}
int ans = 0;
for (int i = 0; i < v.size(); i++) {
ans |= v[i];
}
if (ans != k) {
cout << "Subset does not exist" << endl;
return;
}
cout << "Result = ";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
}
int main(){
int arr[] = { 1, 4, 2 };
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
getSubSet(arr, n, k);
return 0;
}실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Result = 1 2
복잡도 분석
배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)입니다. 추가로 사용되는 공간은 후보 원소들을 저장하는 벡터 공간뿐이며, 최악의 경우 O(n)입니다.