[Leet Code풀이] 713. Subarray Product Less Than K

문제 설명

https://leetcode.com/problems/subarray-product-less-than-k/

자세한 문제는 위 링크 참고. 리스트에 숫자가 주어지면, k 보다 작은 수열을 찾는 문제다. 답을 찾는건 쉬우나, time out 에러를 해결하려면 결국 two pointer로 해결해야 한다.

첫번째 풀이 (타임아웃 에러)

첫번째 시도. 누구나 직관적으로 생각할 수 있는 방법으로 접근했다. left를 하나씩 올려가면서 k 보다 크거나 같은 지점이 나오면 left를 올려서 다시 체크 하는 방식. 문제는 타임아웃에 걸리기 때문에 통과할 수 없다. 생각해보면 이 방법은 이중 루프를 돌기 때문에 최악의 경우 n^2이 나온다.

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # window size 1 -> len(nums)
        
        left =0 
        right = 0
        result = 0
        
        for left in range(len(nums)):
            prod = nums[left]
            if nums[left] < k:
                result += 1
            for right in range(left+1, len(nums)):
                # 범위 검사
                if nums[right] != 1:
                    prod *= nums[right]
                
                if prod < k:
                    result += 1
                else:
                    break
                    
        return result

두번째 풀이

결국 방법이 생각나지 않아서 아래 블로그를 참고하여 코드를 작성했다. https://enumclass.tistory.com/87 기존에 생각하던 방식으로는 타임아웃 에러 때문에 해당 문제를 도저히 풀수가 없었다.

각 0번째 인덱스에서 가능한 경우, 1번째 인덱스에서 가능한 경우 … 등을 구하고 만약 k와 같거나 넘어가는 경우에는 left를 조정하여 값을 구하는 방식이다. 자세한건 위 블로그 참고

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        cnt = 0
        acc = 1
        left = 0
        result = 0
        for i in range(len(nums)):
            cnt = i + 1
            acc *= nums[i]
            
            if k <= 1:
                return 0
            
            # 누적곱이 크면 left를 옮겨가며 체크
            while acc >= k and acc > 1 and left <= i:
                acc = acc//nums[left]
                left += 1
            
            result = result + (cnt - left)
        return result

위 코드로는 Success가 떴다.