문제 설명
양의 정수로 이루어진 배열 nums가 주어졌을 때, 부분 배열에 포함된 모든 원소의 곱이 k보다 작은 연속(contiguous) 부분 배열의 개수를 세어 출력하는 문제입니다.
예를 들어 입력이 [10, 5, 2, 6]이고 k = 100이라면 정답은 8이며, 조건을 만족하는 부분 배열은 다음과 같습니다.
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
풀이 접근: 슬라이딩 윈도우
모든 부분 배열을 하나씩 검사하는 브루트 포스 방식은 비효율적입니다. 대신 슬라이딩 윈도우(투 포인터) 기법을 활용하면 O(n) 시간 안에 문제를 해결할 수 있습니다. 핵심 아이디어는 윈도우의 곱이 k 이상이 되면 왼쪽 끝을 줄여가며 조건을 유지하는 것입니다. 알고리즘 단계는 다음과 같습니다.
- temp := 1, j := 0, ans := 0으로 초기화합니다.
- i를 0부터 배열의 끝까지 순회하며 다음을 수행합니다.
- temp := temp × nums[i] — 윈도우의 오른쪽 끝을 확장하며 곱을 갱신합니다.
- temp ≥ k이고 j ≤ i인 동안, temp := temp ÷ nums[j]로 나누고 j를 1씩 증가시켜 윈도우의 왼쪽 끝을 축소합니다.
- ans := ans + (i − j + 1) — 인덱스 i에서 끝나는 유효한 부분 배열의 개수를 더합니다.
- 순회가 끝나면 ans를 반환합니다.
예제 동작 과정
nums = [10, 5, 2, 6], k = 100일 때 알고리즘이 진행되는 과정을 살펴보겠습니다.
- i = 0: temp = 10 (< 100) → ans += 1 → ans = 1
- i = 1: temp = 50 (< 100) → ans += 2 → ans = 3
- i = 2: temp = 100 (≥ 100) → nums[0] = 10으로 나누어 temp = 10, j = 1 → ans += 2 → ans = 5
- i = 3: temp = 60 (< 100) → ans += 3 → ans = 8
최종적으로 8이 반환되며, 이는 앞서 나열한 부분 배열의 개수와 일치합니다.
C++ 구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
lli temp = 1;
int j = 0;
int ans = 0;
for(int i = 0; i < nums.size(); i++){
temp *= nums[i];
while(temp >= k && j <= i) {
temp /= nums[j];
j++;
}
ans += (i - j + 1);
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {10,5,2,6};
cout << (ob.numSubarrayProductLessThanK(v, 100));
}입력
[10,5,2,6] 100
출력
8
복잡도 분석
포인터 i와 j가 각각 배열을 최대 한 번씩만 순회하므로 시간 복잡도는 O(n)입니다. 또한 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 참고로 곱이 커질 수 있으므로 temp를 long long 타입으로 선언해 오버플로우를 방지하는 것이 안전합니다.