TIL
[코테연습] 2044. Count Number of Maximum Bitwise-OR Subsets
크라00
2024. 10. 18. 17:18
- 배열 / 백트래킹 / 이진수 문제
문제 분석
- 부분집합의 정의:
- 주어진 배열 nums에서 일부 또는 전체 요소를 선택하여 부분집합을 구성합니다.
- 두 부분집합은 선택된 요소들의 인덱스가 다를 경우 서로 다른 것으로 간주합니다.
- 예를 들어, 배열 [1, 2, 3]의 부분집합은 [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3], []입니다.
- 비트 OR 연산:
- 주어진 배열의 부분집합에서 모든 요소를 비트 OR 연산으로 결합하여 값 d를 계산합니다.
- 예를 들어, 부분집합 [1, 2]에 대해 비트 OR 연산을 하면 1 | 2 = 3이 됩니다.
- 이 과정을 모든 부분집합에 대해 수행하여 최대 OR 값을 구하고, 그 값과 동일한 부분집합의 개수를 세야 합니다.
- 구해야 할 것:
- nums 배열의 부분집합 중 최대 비트 OR 값을 구합니다.
- 해당 최대 값을 가지는 부분집합의 개수를 반환합니다.
문제 해결을 위한 접근 방법
- 모든 부분집합 생성:
- 이 문제는 모든 부분집합을 생성해 볼 필요가 있습니다.
- 부분집합을 생성하는 방법으로는 재귀적인 백트래킹 혹은 비트마스킹 기법이 있습니다.
- 최대 OR 값을 계산:
- 배열의 모든 부분집합에 대해 비트 OR 연산을 계산하여, 그 중 최대 OR 값을 찾습니다.
- 최대 OR 값을 미리 계산한 후, 백트래킹 과정에서 각 부분집합의 OR 값이 최대 값과 같은지를 비교하면서 그 개수를 셉니다.
- 시간 복잡도:
- 이 문제는 모든 부분집합을 계산하는 것이므로 시간 복잡도는 O(2^n)입니다. n은 nums 배열의 길이입니다.
- nums의 최대 길이가 16으로 주어지기 때문에, 부분집합의 수는 최대 2^16 = 65536입니다. 이는 일반적인 알고리즘에서 허용 가능한 수준입니다.
해결 방법
- 백트래킹 방법:
- 재귀 함수를 사용하여 각 인덱스에서 요소를 포함하거나 포함하지 않는 두 가지 선택지를 통해 모든 부분집합을 생성합니다.
- 생성된 부분집합의 OR 값을 계속 계산하여 최대 값을 찾고, 동일한 값의 부분집합의 개수를 셉니다.
- 비트마스킹 방법:
- 비트마스킹을 사용하면 반복문을 통해 모든 가능한 부분집합을 생성할 수 있습니다.
- 각 부분집합은 인덱스를 비트로 표현하여 계산할 수 있습니다. 예를 들어, [1, 2, 3] 배열에 대해 001, 010, 011 등으로 부분집합을 표현하는 방식입니다.
> java
class Solution {
int cnt = 0;
public int countMaxOrSubsets(int[] nums) {
int n = nums.length;
cnt = 0;
int max = 0;
for (int num : nums) {
max = num | max;
}
backtrack(nums, 0, new int[n], 0, max);
return cnt;
}
void backtrack(int[] arr, int index, int[] output, int depth, int max) {
int[] rs = Arrays.copyOf(output, depth);
if (rs.length > 0) {
int d = rs[0];
for (int i = 1; i < rs.length; i++) {
d = d | rs[i];
}
if (d >= max) {
cnt++;
}
}
for (int i = index; i < arr.length; i++) {
output[depth] = arr[i];
backtrack(arr, i + 1, output, depth + 1, max);
}
}
}
> python
class Solution:
def __init__(self) :
self.cnt = 0
def countMaxOrSubsets(self, nums: List[int]) -> int:
n = len(nums)
self.cnt = 0
max_num = 0
for num in nums : max_num = max_num | num
self.backtrack(nums, 0, [], 0, max_num)
return self.cnt
def backtrack(self, arr: List[int], index : int, output : List[int], depth : int, max_num : int) :
rs = output[:depth]
if len(rs) > 0 :
d = rs[0]
for i in range(1,len(rs)) :
d = d | rs[i]
if d == max_num : self.cnt+=1
for i in range(index, len(arr)) :
output.append(arr[i])
self.backtrack(arr, i+1, output, depth+1, max_num)
output.pop()
- 문제 해결 후 알게 된점
1. 백트래킹 접근 방식에 대한 다양화
2. 파이썬 코드로 백트래킹 방식 체득