[leetcode] 3097. Shortest Subarray With OR at Least K II #2

안녕하세요. 이번에는 어제 풀었던 [leetcode] 3097. Shortest Subarray With OR at Least K II를 다시 풀어보려고 합니다.
 
다시 풀어보는 이유는 당연하게도 실행 시간의 효율성이 낮기 때문입니다!

실행 시간 20%!!!

• 참고: https://goodahn.tistory.com/244

1. 이전 문제 풀이의 비효율적인 연산

저는 이전에 문제를 풀 때 OR 연산을 수행하기 위해서 파이썬의 bin 함수를 사용한 것이 걸리더라고요.
 
bin 함수는 주어진 수에 대해서 2진법 문자열을 반환하는 함수입니다.
2진법 문자열을 만들기 위해서는 여러 비트 연산과 메모리를 사용해야 할텐데 이 부분을 해소해보기로 했습니다.
 
bin 함수를 사용해서 2진법 문자열을 얻는 대신 비트 연산인 AND, OR 연산을 이용할 것입니다!
 

2. 수정된 코드

다음과 같이 bin 함수 사용 부분을 수정하니 runtime이 약 70%까지 개선될 수 있었습니다!
여기까지 개선하고 다른 문제로 넘어가보겠습니다 ㅎㅎ

• 사실 이것저것 많이 시도해봤는데 더 이상의 진전이 없었습니다 푸ㅠㅠㅠ

개선된 실행 시간!

 
원래 코드

def add_bin(ones, num):
    bin_num = bin(num)[2:]
    for i in range(len(bin_num)):
        if bin_num[-1-i] == '1':
            ones[-1-i] += 1

def extract_one_by_num(ones, num):
    bin_num = bin(num)[2:]
    for i in range(len(bin_num)):
        if bin_num[-1-i] == '1':
            ones[-1-i] =  max(0, ones[-1-i]-1)

 
수정된 코드

def add_bin(ones, num, curr):
    for i in range(31):
        if num & (1 << i):
            ones[-1-i] += 1
    return curr|num

def extract_one_by_num(ones, num, curr):
    for i in range(31):
        if num & (1 << i):
            ones[-1-i] = ones[-1-i]-1
            if ones[-1-i] == 0:
                curr -= (1 << i)
    return curr

 

+ 코드

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        left_idx, right_idx = 0, 0
        min_length = float("inf")
        ones = [0] * 32
        curr = 0

        while right_idx < len(nums):
            curr = add_bin(ones, nums[right_idx], curr)
            while curr >= k and left_idx <= right_idx:
                curr = extract_one_by_num(ones, nums[left_idx], curr)
                min_length = min(min_length, right_idx - left_idx + 1)
                left_idx += 1
            right_idx += 1
        if min_length == float("inf"):
            return -1
        return min_length

def add_bin(ones, num, curr):
    for i in range(31):
        if num & (1 << i):
            ones[-1-i] += 1
    return curr|num

def extract_one_by_num(ones, num, curr):
    for i in range(31):
        if num & (1 << i):
            ones[-1-i] = ones[-1-i]-1
            if ones[-1-i] == 0:
                curr -= (1 << i)
    return curr