2044. Count Number of Maximum Bitwise-OR Subsets

Problem : https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:11:57

 

---

 

문제 설명

 

정수 배열 nums가 주어질때, nums의 부분집합을 bitwise OR 연산하였을 때 가능한 가장 큰 값을 찾고, 최대 bitwise OR값을 도출하는 공집합이 아닌 서로 다른 부분집합의 개수를 반환하라.

 

어떤 배열 a가 어떤 배열 b의 부분집합이려면, a는 b에서 특정 원소(0개도 가능)를 제거함으로써 얻어질 수 있어야 한다. 두 부분집합은 선택된 원소의 인덱스가 다르다면 다르다고 취급된다.

 

어떤 배열 a의 bitwise OR은 a[0] OR a[1] OR ... a[a.length - 1]로 정의된다.(0-인덱스임)

---

 

풀이

 

bitwise 연산을 염두해 두자. 모든 부분집합의 경우의 수를 구하려면 최대 2^16번의 연산을 수행해야 하므로 옳은 선택이 아닌 것 같다.

우리는 DP를 고려해볼 수 있다.

 

가령, 앞선 부분집합들의 결과로 n이라는 bitwise OR 경우의 수가 m개 생성되었다고 하자. 이제 새로운 정수 k를 다음과 같이 적용해 볼 수 있다.

• k를 사용하지 않는다 -> 다음 결과(n)로 m개가 더해진다.
• k를 사용한다 -> 다음 결과(n|k)로 m개가 더해진다.

위 방식으로 정수 k까지의 집합에서 부분집합으로 bitwise OR을 수행한 경우의 수를 모두 구할 수 있겠다. k가 nums의 마지막 자연수가 될 때까지 반복하면, 최후에는 전체 집합의 경우의 수가 도출된다. 가방 문제를 떠올리면 이해가 빠를 것이다.

시간복잡도는 O(N * M)이지만(N = nums의 길이, M = max bitwise OR 결과), 중첩되는 경우들에 의해 실제 경우의 수는 더 적을 것이다. N <= 16, M < =10^5므로 충분히 합리적이라고 볼 수 있다. 

 

풀이 코드

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        maxBit = 0
        for n in nums :
            maxBit |= n
        
        dp = defaultdict(int)
        dp[0] = 1
        for n in nums :
            next_dp = defaultdict(int)
            for m, cnt in dp.items() :
                next_dp[m] += cnt
                next_dp[m|n] += cnt
            dp = next_dp
        return dp[maxBit]