[2024] day 88. Leetcode 713. Subarray Product Less Than K

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

2024년 3월 27일 (수)
Leetcode daily problem

713. Subarray Product Less Than K

https://leetcode.com/problems/subarray-product-less-than-k/?envType=daily-question&envId=2024-03-27

Problem

배열에서의 곱이 주어진 값 k보다 작은 부분 배열의 개수를 찾는 것이다.

Solution

sliding window

해당 문제는 슬라이딩 윈도우 기법을 사용해서 해결할 수 있다.
배열을 순회하면서 연속된 부분 배열을 검사하고, 부분 배열의 시작고 끝 지점을 조절해가면서 원하는 조건을 만족시키는 부분 배열을 찾는다.

두 개의 포인터를 사용해서 부분 배열의 시작과 끝을 나타내고, 시작 포인터를 배열의 첫 번째 요소로 초기화하고 끝 포인터를 시작 포인터와 같은 위치로 설정한다.
끝 포인터를 오른쪽으로 이동시키면서 곱을 계산하고, 곱이 k보다 작을 때 까지 이동한다. 곱이 k보다 작아질 때마다 가능한 부분 배열의 개수를 추가한다. (끝 포인터 - 시작 포인터 +1)
곱이 k보다 커지거나 배열의 끝에 도달할 때 까지 반복한다.
반복이 끝나면 시작 포인터를 오른쪽으로 이동하고 다시 반복한다. 모든 요소에 대한 반복이 끝나면 부분 배열의 개수를 반환한다.

Code

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if k <= 1:
            return 0

        product = 1
        count = 0
        left = 0

        for right in range(len(nums)):
            product *= nums[right]

            while product >= k:
                product /= nums[left]
                left += 1

            count += right - left + 1

        return count

Complexicity

시간 복잡도

while 루프를 이용해 곱이 k를 초과할 때 까지 왼쪽으로 포인터를 이동시키크로 O(n)의 시간복잡도를 가진다.

공간 복잡도

입력 크기와 무관하게 상수 변수를 사용하므로 공간복잡도는 O(1)이다.