문제 개요
양의 정수로 이루어진 배열 A와 두 개의 양의 정수 L, R이 주어집니다. 이때, 부분 배열 안의 최댓값이 L 이상 R 이하가 되는 (연속된, 비어 있지 않은) 부분 배열의 개수를 구하는 것이 목표입니다.
예를 들어 A = [2,1,4,3], L = 2, R = 3이라고 해보겠습니다. 조건을 만족하는 부분 배열은 [2], [2,1], [3]으로 총 세 가지이므로 정답은 3이 됩니다.
접근 방법
이 문제는 각 인덱스를 끝점으로 하는 유효한 부분 배열의 개수를 누적하는 방식으로 선형 시간(O(n))에 해결할 수 있습니다. 핵심 변수는 다음과 같습니다.
- ret: 지금까지 찾은 유효한 부분 배열의 총개수
- dp: 현재 인덱스 i를 끝으로 하는 유효한 부분 배열의 개수
- prev: 마지막으로 R보다 큰 값(경계를 깨는 값)이 등장한 인덱스
알고리즘 진행 순서는 다음과 같습니다.
- ret := 0, dp := 0, prev := -1로 초기화합니다.
- i를 0부터 배열 크기 - 1까지 반복합니다.
- A[i] < L이고 i > 0인 경우: 현재 원소는 범위보다 작지만 앞선 유효한 부분 배열을 그대로 확장할 수 있으므로 ret에 dp를 더합니다.
- A[i] > R인 경우: 이 위치를 포함하는 부분 배열은 절대 유효할 수 없으므로 prev := i, dp := 0으로 초기화합니다.
- L ≤ A[i] ≤ R인 경우: prev 다음 위치부터 i까지 시작하는 모든 부분 배열이 유효하므로 dp := i - prev로 갱신하고 ret에 더합니다.
- 반복이 끝나면 ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 동작 과정을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int ret = 0;
int dp = 0;
int prev = -1;
for(int i = 0; i < A.size(); i++){
if(A[i] < L && i > 0){
ret += dp;
}
if(A[i] > R){
prev = i;
dp = 0;
}
else if(A[i] >= L && A[i] <= R){
dp = i - prev;
ret += dp;
}
}
return ret;
}
};
main(){
vector<int> v = {2,1,4,3};
Solution ob;
cout << (ob.numSubarrayBoundedMax(v, 2, 3));
}실행 결과
입력:
[2,1,4,3] 2 3
출력:
3
마무리
이 풀이는 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)입니다. 브루트포스 방식(모든 부분 배열을 검사하는 O(n²))과 비교했을 때 훨씬 효율적이며, dp와 prev 두 변수만으로 상태를 관리한다는 점이 핵심 아이디어입니다.