3097. Shortest Subarray With OR at Least K II

Problem : https://leetcode.com/problems/shortest-subarray-with-or-at-least-k-ii/

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:19:02

 

---

 

문제 설명

 

 

음이 아닌 정수로 구성된 배열 nums와 정수 k가 주어진다.

 

어떤 배열이 특별하다는 의미는 그 배열에 속한 모든 원소들의 비트 OR이 적어도 k이상일 때를 의미한다.

 

nums의 부분 배열 중 가장 짧은 길이의 특별한 부분 배열의 길이를 반환하라. 만약 그러한 부분 배열이 없다면 -1을 출력하라.

---

 

풀이

 

 

풀이 코드

class Solution:
    def add(self, num) :
        for i in range(self.length) :
            if num & (1 << i) :
                self.check[i] += 1
    
    def discard(self, num) :
        for i in range(self.length) :
            if num & (1 << i) :
                self.check[i] -= 1

    def convert(self) :
        return sum([ 1 << k for k, v in self.check.items() if v > 0])

    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        self.length = len(bin(max(nums))) - 2
        self.check = defaultdict(int)

        result = len(nums) + 1
        q = deque()
        for n in nums :
            q.append(n)
            self.add(n)
            while q and self.convert() >= k :
                result = min(result, len(q))
                tmp = q.popleft()
                self.discard(tmp)
        return result if result < len(nums) + 1 else -1