C++로 풀어보는 유효한 부분 배열 개수 문제 – 단조 스택 활용법

문제 이해하기

정수로 이루어진 배열 A가 주어졌을 때, 다음 조건을 만족하는 비어 있지 않은 연속된 부분 배열(subarray)의 개수를 구하는 것이 목표입니다.

조건: 부분 배열의 가장 왼쪽(첫 번째) 원소가, 그 부분 배열에 포함된 나머지 모든 원소보다 작거나 같아야 합니다.

예시

입력이 [1, 4, 2, 5, 3]이라면 정답은 11입니다. 조건을 만족하는 부분 배열은 다음과 같습니다.

[1], [4], [2], [5], [3], [1,4], [2,5], [1,4,2], [2,5,3], [1,4,2,5], [1,4,2,5,3]

접근 방법: 단조 스택(Monotonic Stack)

이 문제는 단조 스택 기법을 사용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 스택을 활용해 현재 위치에서 끝나는 유효한 부분 배열의 개수를 누적하는 것입니다.

알고리즘 단계

1. 결과값 ret을 0으로 초기화하고, 정수를 저장할 스택 st를 선언합니다.
2. 배열의 각 원소 x = nums[i]를 순서대로 확인합니다.
3. 스택이 비어 있지 않고, 스택의 최상단 값이 x보다 크다면 계속 pop 합니다. (이렇게 제거된 원소들은 더 이상 왼쪽 끝 원소 역할을 할 수 없습니다.)
4. x를 스택에 push 합니다.
5. 현재 스택의 크기를 ret에 더합니다. 스택에 남아 있는 각 원소는 현재 인덱스 i에서 끝나는 유효한 부분 배열의 시작점이 될 수 있기 때문입니다.
6. 모든 순회가 끝나면 ret을 반환합니다.

스택은 항상 아래에서 위로 오름차순(같은 값 허용) 상태를 유지하므로, 각 원소는 최대 한 번 push되고 한 번 pop됩니다. 따라서 전체 시간 복잡도는 O(n), 공간 복잡도는 최악의 경우 O(n)입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int validSubarrays(vector<int>& nums) {
      int ret = 0;
      int n = nums.size();
      stack <int> st;
      for(int i = 0; i < nums.size(); i++){
         int x = nums[i];
         while(!st.empty() && x < st.top()) st.pop();
         st.push(x);
         ret += st.size();
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,4,2,5,3};
   cout << (ob.validSubarrays(v));
}

실행 결과

입력

{1,4,2,5,3}

출력

11

마무리

단조 스택은 "각 원소를 기준으로 왼쪽/오른쪽 경계를 찾는" 유형의 문제에서 매우 강력한 도구입니다. 이 문제처럼 부분 배열의 개수를 세거나, 다음으로 큰/작은 원소를 찾는 문제에서 자주 활용되니 응용 사례를 함께 학습해 두면 좋습니다.