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

안녕하세요. 오늘은 leetcode에서 3097. Shortest Subarray With OR at Least K II 문제를 풀어봤습니다.

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

1. 문제

이 문제에서는 음수가 아닌 수로 이루어진 수열 nums와 자연수 k가 주어졌을 때, 길이가 가장 짧은 special한 연속된 부분 수열의 길이를 찾아야 합니다.

• 수열 내의 모든 수를 OR 연산했을 때 k보다 크거나 같으면 special 하다고 합니다.
• nums의 길이는 최대 2 * 10^5

1.1. 부분 수열

부분 수열이란 주어진 수열에서 일부 숫자들을 원래 순서대로 나열한 수열입니다.

• 주어진 수열에서의 순서를 지켜야만 합니다!

1, 2, 3, 4, 5 부분 수열 예시

• O: 1, 3, 4, 5
• O: 4, 5
• O: 2, 5
• X: 2, 1, 5
• X: 5, 1
• X: 3, 2, 4

1.2. 연속 부분 수열

연속 부분 수열은 부분 수열 중에서 원래 수열의 연속된 수들만 나열한 수열입니다.

 

1, 2, 3, 4, 5 연속 부분 수열 예시

• O: 1, 2, 3
• O: 3, 4, 5
• X: 1, 3, 4
• X: 2, 5

1.3. OR 연산

OR 연산은 AND 연산과 비슷합니다.

 

1. OR 연산에 사용되는 두 숫자를 모두 2진법으로로 표현합니다.

2. 두 수 중 하나라도 1을 가지고 있는 자리 수가 있다면 해당 자리 수에 1을 남깁니다.

 

OR 연산 예시

• 2 OR 3
  1. 2진법으로 표현하기: 2 => 10, 3 => 11
  2. 두 수 중 하나라도 1을 가지고 있는 자리 수가 있다면 해당 자리 수에 1을 남기기: 10 OR 11 => 11
• 3 AND 8
  1. 2진법으로 표현하기: 3 => 11, 8 => 1000
  2. 두 수 중 하나라도 1을 가지고 있는 자리 수가 있다면 해당 자리 수에 1을 남기기 : 11 OR 1000 => 1011
• 3 AND 7
  1. 2진법으로 표현하기: 3 => 11, 7 => 111
  2. 두 수 중 하나라도 1을 가지고 있는 자리 수가 있다면 해당 자리 수에 1을 남기기 : 11 OR 111 => 111

2. 문제 풀이

2.1. brute force

가장 간단한 방법은 주어진 수열에 대해서 모든 연속 부분 수열이 special 한지 확인하고 길이가 가장 짧은 연속 부분 수열의 길이를 반환하는 것입니다.

이 방법은 O(n^2) 시간복잡도를 가지게 됩니다.

• 길이 1인 연속 부분 수열 n개
• 길이 2인 연속 부분 수열 n-1개
• 길이 3인 연속 부분 수열 n-2개
• ...
• 길이 n인 연속 부분 수열 1개
• => n^2

nums의 길이가 최대 2*10^5이므로 O(n^2) 시간복잡도를 가지는 알고리즘은 시간 내에 답을 찾아내지 못합니다 ㅜ

다른 방법이 필요합니다.

2.2. binary search

모든 경우의 수를 확인하는 brute force의 개선 방법으로는 binary search가 있습니다.

문제는 binary search를 어떻게 적용하느냐는 것이죠. 생각보다 단순합니다.

 

1. 길이 n인 연속 부분 수열이 special한지 확인한다.

2. 1의 연속 부분 수열이 special 했다면 길이 n/2인 연속 부분 수열이 special한지 확인한다.

3. 2의 연속 부분 수열이 special 했다면 길이 n/4인 연속 부분 수열이 special한지 확인한다.

4. ...

이런 식으로 연속 부분 수열의 길이를 좁혀나가는 것입니다.

 

이렇게만 하더라도 시간복잡도를 O(nlogn)으로 낮출 수 있습니다.

2.3. sliding window

binary search에서 더 나아간 방법이 바로 sliding window 방식입니다.

방법은 다음과 같습니다.

 

1. 수열의 처음부터 시작해서 special한 연속 부분 수열을 찾을 때까지 수열의 길이를 늘리고

2. special한 연속 부분 수열을 찾으면 special하지 않을 때까지 연속 부분 수열의 앞부분을 제거합니다.

3. 1-2를 반복합니다.

 

+코드

제 코드도 공유드립니다...!

Runtime의 효율이 부족한데 다음에는 이를 개선할 수 있는 방법을 찾아봐야겠습니다.

개선이 필요한 결과!

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

        while right_idx < len(nums):
            add_bin(ones, nums[right_idx])
            while bin_to_digit(ones) >= k and left_idx <= right_idx:
                extract_one_by_num(ones, nums[left_idx])
                if min_length > right_idx - left_idx + 1:
                    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):
    bin_num = bin(num)[2:]
    for i in range(len(bin_num)):
        if bin_num[-1-i] == '1':
            ones[-1-i] += 1

def bin_to_digit(ones):
    result = 0
    for i in range(len(ones)):
        if ones[len(ones)-1-i] > 0:
            result += pow(2, i)
    return result

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)