LeetCode - 898 - bitwise Ors of Subarrays - swift

https://leetcode.com/problems/bitwise-ors-of-subarrays

Bitwise ORs of Subarrays - LeetCode

 

꽤 어려웠다. 이해하기까지 시간이 걸렸던 문제다. 

간단하게 생각하면, 모든 부분연속수열들를 구하여 OR연산하면 되겠지만, 

우선 숫자들의 갯수가 최대 5만개이므로, 시간초과가 난다.

 

조금만 고민해보면, 다음과 같이 알수있다. 

 

주어진 숫자배열을 arr [ i ] 이라고하고, arr의개수를 N 이라하자. 

부분연속수열들의 OR연산한값을 con[ i ] [ j ] =  arr[i] | arr [ i+1] | ... arr[ j ]  이라하자. 

 

i 가 0 부터 N-1까지 범위가있다고했을때, 

con [ i ] [ N-1]  의 총 최대개수는 몇개가나올까? 

즉  아래의 set , 유니크한 개수는 몇개일까 ?

var set = Set<Int>()
for i in 0..<N {
    set.insert( con[i][N-1] ) 
}

print( set.count ) 

즉, 아래와같이 파란색부분들의 유니크한개수가 몇개가나올까? 

 

 

각 숫자들의 값은 최대 10억까지인점을 고려하면,

잘생각해보면,

숫자들의개수가 아무리많아도,  최대 30개란걸 알수있다. 

최대인경우, 즉 최악의경우는 1, 2, 4 , 8 , ...  2^30, 즉 2의 배수로만 이루어진 숫자배열인경우에 최악의경우, 30개가나올수있다. 

 

왜냐하면, con[ 0 ] [ 4 ] 는 con [ 1 ] [ 4 ] 보다 크거나같을수밖에없다. 

즉 con [ 0 ] [ N ] 은 con [ 1 ] [ N ] 의 비트들을 모두 아우를수밖에없다. 

마찬가지로 con [ 1 ] [ N ] 은 con [ 2 ] [ N ] 의 비트들을 모두 아우를 수밖에없다. 

 

여기까지만 이해했다면 이제 충분히 풀수있는문제가된다. 

 

각 arr의 위치마다, 최대30개를 넘지않는 OR연산한값들로만 OR연산하면되기 때문이다. 

즉 시간복잡도가 O(30*N)으로 구할수있게된다. 

 

 

class Solution {
    func subarrayBitwiseORs(_ arr: [Int]) -> Int {
        var ans = Set<Int>()
        var keep = Set<Int>()
        
        for i in 0..<arr.count {
            var tempt = Set<Int>()
            tempt.insert(arr[i])
            keep.forEach { tempt.insert($0|arr[i])}
            keep = tempt
            tempt.forEach{ans.insert($0)}
        }
        return ans.count
    }
}
print(Solution().subarrayBitwiseORs([0]))