[2024] day 92. Leetcode 2444. Count Subarrays With Fixed Bounds

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 31일 (일)
Leetcode daily problem

992. Subarrays with K Different Integers

https://leetcode.com/problems/subarrays-with-k-different-integers/?envType=daily-question&envId=2024-03-30

Problem

정수 배열 nums와 두 개의 정수 minK 및 maxK가 제공될 때,
'fixed-bound subarray'를 충족하는 하위 배열의 수를 반환한다.
해당 하위 배열은 배열에서 연속되면서

• 하위 배열의 최소값은 minK와 같고,
• 하위 배열의 최대값은 maxK와 같다.

Solution

two pointer

해당 문제는 two-pointers로 특정 조건을 만족하는 subarray나 부분집합을 찾아서 해결한다.

두 개의 포인터를 사용해서 subarray 내의 최솟값과 최댓값이 주어진 값과 같도록 minK, maxK의 구간을 찾기 위해 두 개의 포인터를 사용해 윈도우를 이동한다.
현재 인덱스를 기준으로 가능한 subarray 개수를 파악한다. 이 때 가능한 subarray의 개수는 현재 인덱스부터 왼쪽에 있는 minK를 만족하는 인덱스와 오른쪽에 있는 maxK를 만족하는 인덱스 중에서 가장 작은 인덱스를 선택하고, 조건에 맞지 않은 인덱스를 뺀 값이다.

subarray 내에 minK보다 작은 값이 있으면 subarray는 조건을 만족하지 않게 되고 max(0, min(left_idx, right_idx) - cur_idx)로 인덱스를 기준으로 minK, maxK를 만족하는 subarray의 개수를 계산할 때 bad_idx 이후의 subarray는 포함하지 않게 한다.

Code

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        ans = 0
        left, right, idx = -1, -1, -1
        
        for i, num in enumerate(nums):
            if not minK <= num <= maxK:
                idx = i
            
            if minK == num:
                left = i
            
            if maxK == num:
                right = i
                
            ans += max(0, min(left, right)-idx)
            
        return ans

Complexicity

시간 복잡도

주어진 배열 nums를 순회할 때 O(n)이 소요된다.

공간 복잡도

상수변수만 할당하므로 해당 코드의 시간복잡도는 O(1) 이다.

---

사실 해당 문제를 엄청 복잡하게 푼 솔루션으로 이해했는데,
베스트 솔루션에서 해당 알고리즘으로 손쉽게 푸는 방법을 발견했다..
쏘 지니어스.... 이렇게 간단하게 풀리다니

처음 보고 이해했던 코드는 이거였다

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        def findArrays(nums, minK, maxK):
            nums.append(0)
            res = []
            arr = []
            for i in range(len(nums)):
                if nums[i] >= minK and nums[i] <= maxK:
                    arr.append(nums[i])
                else:
                    if arr and min(arr)==minK and max(arr)==maxK:
                        res.append(arr)
                    arr = []
            return res
        
        def calculateSubarrays(arr, minK, maxK):
            res = 0
            queue = []
            prev = 0
            n = len(arr)
            if minK==maxK:
                return n//2*(n+1) if n%2==0 else (n+1)//2*n
            for i in range(len(arr)):
                if i>=prev and (arr[i] == minK or arr[i] == maxK):
                    while len(queue)>0 and arr[queue[len(queue)-1]] !=arr[i]:
                        index = queue.pop(0)
                        beforeCount = index -prev+1
                        afterCount = n - i
                        res += beforeCount*afterCount
                        prev = index+1
                    queue.append(i)
            return res

        arrs = findArrays(nums, minK, maxK)
        ans = 0
        for arr in arrs:
            ans+=calculateSubarrays(arr, minK, maxK)
        return ans