문제 개요
정수 배열 A가 주어졌을 때, 램프(ramp)란 i < j이면서 A[i] <= A[j]를 만족하는 인덱스 쌍 (i, j)를 의미하며, 이때 램프의 너비는 j - i로 정의됩니다. 목표는 배열 A에서 가장 넓은 램프의 너비를 구하는 것이고, 만약 램프가 하나도 존재하지 않는다면 0을 반환해야 합니다.
예를 들어 입력이 [6,0,8,2,1,5]라고 한다면 결과는 4가 됩니다. 최대 너비 램프는 (i, j) = (1, 5)에서 만들어지는데, A[1] = 0이고 A[5] = 5이므로 너비는 5 - 1 = 4입니다.
알고리즘 접근 방법
이 문제는 단조 감소 스택(monotonic decreasing stack)을 활용하면 선형 시간에 해결할 수 있습니다. 풀이 과정은 다음과 같습니다.
배열 v를 생성하고, n을 주어진 배열의 크기로, ret을 0으로 초기화합니다.
정수를 저장하는 스택 st를 정의합니다.
i를 0부터 n - 1까지 순회하면서, 스택이 비어 있거나 스택 꼭대기 인덱스의 값이 A[i]보다 크면 i를 스택에 삽입합니다. 이 과정을 거치면 스택에는 값이 점점 작아지는(내림차순) 인덱스들만 남게 됩니다.
이어서 i를 n - 1부터 ret + 1까지 역방향으로 순회하면서, 스택이 비어 있지 않고 A[st.top()] <= A[i]를 만족하는 동안 다음을 반복합니다.
ret을 max(ret, i - st.top())으로 갱신합니다.
스택에서 요소를 제거(pop)합니다.
모든 순회가 끝나면 ret을 반환합니다.
C++ 구현 코드
아래 예제를 통해 실제 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxWidthRamp(vector<int>& A) {
vector < pair <int, int> > v;
int n = A.size();
int ret = 0;
stack <int> st;
for(int i = 0; i < n; i++){
if(st.empty() || A[st.top()] > A[i]){
st.push(i);
}
}
for(int i = n - 1; i > ret; i--){
while(!st.empty() && A[st.top()] <= A[i]){
ret = max(ret, i - st.top());
st.pop();
}
}
return ret;
}
};
main(){
vector<int> v1 = {6,0,8,2,1,5};
Solution ob;
cout << (ob.maxWidthRamp(v1));
}입력
[6,0,8,2,1,5]
출력
4
동작 원리 및 복잡도 분석
첫 번째 순회에서는 앞으로 더 작은 값이 나타날 가능성이 있는 인덱스만 스택에 보관합니다. 즉, 새로운 값이 스택 꼭대기의 값보다 작을 때만 push하므로 스택은 항상 내림차순을 유지하게 됩니다.
두 번째 순회에서는 배열의 오른쪽 끝에서 왼쪽으로 이동하며, 현재 값 A[i]보다 작거나 같은 스택의 인덱스를 만날 때마다 램프 너비를 계산합니다. 오른쪽에서부터 탐색하기 때문에 자연스럽게 더 넓은 램프를 우선적으로 발견하게 되고, 현재 ret보다 좁은 구간은 검사 대상에서 제외되므로 탐색 범위가 빠르게 줄어듭니다.
각 인덱스는 최대 한 번 push되고 한 번 pop되므로 전체 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 이는 모든 (i, j) 조합을 확인하는 브루트 포스 방식의 O(n²)보다 훨씬 효율적인 접근법입니다.