곱이 기준보다 작은 연속 구간 개수

자바스크립트 코딩테스트 문제로 multiplicative-window 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium multiplicative-window 함수명: countProductUnderLimitWindows 제한 시간: 500ms

양의 정수 배열 nums와 기준값 limit이 주어질 때, 곱이 limit보다 작은 연속 구간의 개수를 반환하는 countProductUnderLimitWindows 함수를 작성하세요.

문제 설명

연속 구간은 배열에서 끊기지 않고 이어지는 일부 원소입니다.

예를 들어 nums = [10, 5, 2, 6], limit = 100일 때 [10, 5]의 곱은 50이라 조건을 만족하지만, [10, 5, 2]의 곱은 100이라 조건을 만족하지 않습니다.

곱이 limit보다 작은 연속 구간의 총개수를 구하세요.

제한사항

1 <= nums.length <= 100000
1 <= nums[i] <= 1000
1 <= limit <= 1000000000
연속 구간의 곱이 limit과 정확히 같으면 조건을 만족하지 않습니다.
반환값은 조건을 만족하는 연속 구간의 개수입니다.
모든 원소가 양의 정수이므로, 윈도우의 왼쪽을 줄이면 곱은 커지지 않습니다.

예시

입력: nums = [10, 5, 2, 6], limit = 100 -> 출력: 8
입력: nums = [1, 1, 1], limit = 2 -> 출력: 6
입력: nums = [3, 4, 5], limit = 1 -> 출력: 0
입력: nums = [100], limit = 100 -> 출력: 0

힌트

오른쪽 포인터를 한 칸씩 늘리며 현재 윈도우의 곱을 유지해 보세요.
곱이 limit 이상이 되면 조건을 만족할 때까지 왼쪽 포인터를 이동합니다.
어떤 오른쪽 끝점 right에서 조건을 만족하는 윈도우가 [left..right]라면, 그 안에서 끝이 right인 더 짧은 구간들도 모두 조건을 만족합니다.

해설

모든 원소가 양수라는 조건이 핵심입니다. 현재 윈도우의 곱이 너무 커졌을 때 왼쪽 원소를 하나씩 빼면 곱은 줄어들거나 그대로 유지됩니다. 따라서 투 포인터로 유효한 윈도우를 유지할 수 있습니다.

오른쪽 포인터 right를 이동할 때마다 nums[right]를 현재 곱에 곱합니다. 만약 현재 곱이 limit 이상이면, left가 가리키는 값을 나누고 left를 오른쪽으로 옮깁니다. 이 과정을 곱이 다시 limit보다 작아질 때까지 반복합니다.

이제 윈도우 [left..right]의 곱이 조건을 만족한다면, 끝점이 right인 유효 구간은 다음처럼 right - left + 1개입니다.

[right]
[right - 1..right]
…
[left..right]

예를 들어 nums = [10, 5, 2, 6], limit = 100에서 right가 마지막 값 6에 있을 때 유효 윈도우는 [5, 2, 6]입니다. 따라서 끝이 6인 유효 구간은 [6], [2, 6], [5, 2, 6] 세 개입니다.

limit이 1이면 모든 원소가 1 이상이므로 어떤 양의 정수 곱도 1보다 작을 수 없습니다. 이런 경우 자연스럽게 답은 0입니다.

각 원소는 오른쪽 포인터로 한 번 들어오고, 왼쪽 포인터로 많아야 한 번 빠집니다. 따라서 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과