히스토그램(histogram)은 너비가 1인 여러 막대가 나란히 이어진 그래프로, 각 막대의 높이는 서로 다를 수 있습니다. 이 글에서는 스택(stack) 자료구조를 활용해 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 구하는 C++ 프로그램을 소개합니다. 스택 기반 접근 방식을 사용하면 모든 막대를 한 번씩만 처리하므로 O(n)의 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다.
getArea() 함수의 알고리즘
스택을 이용한 핵심 아이디어는 각 막대를 "그 막대의 높이를 유지하면서 좌우로 확장할 수 있는 가장 넓은 범위"의 기준으로 삼는 것입니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 빈 스택을 생성하고 최대 넓이(largest_area)를 0으로 초기화합니다.
- 첫 번째 막대부터 마지막 막대까지(i = 0부터 n 미만까지) 반복합니다.
- 스택이 비어 있거나 현재 막대 hist[i]의 높이가 스택 맨 위 막대보다 크거나 같으면, 인덱스 i를 스택에 push합니다.
- 그렇지 않다면 현재 막대가 스택 맨 위 막대보다 작은 경우이므로, 스택 맨 위가 현재 막대보다 큰 동안 계속 pop합니다. pop된 막대를 높이로 하는 직사각형의 넓이를 계산하는데, 이때 스택에 남아 있는 바로 이전 원소가 왼쪽 경계, 현재 인덱스 i가 오른쪽 경계가 됩니다.
- 모든 막대를 처리한 후에도 스택에 막대가 남아 있다면, 남은 막대들을 하나씩 pop하면서 각 막대를 최소 높이로 하는 직사각형의 넓이를 계산합니다.
예제 코드
#include<iostream>
#include<stack>
using namespace std;
int getArea(int hist[], int n)
{
stack<int> st;
int largest_area = 0;
int top;
int toparea;
int i = 0;
while (i < n)
{
if (st.empty() || hist[st.top()] <= hist[i])
st.push(i++);
else
{
top = st.top();
st.pop();
toparea = hist[top] * (st.empty() ? i :
i - st.top() - 1);
if (largest_area < toparea)
largest_area = toparea;
}
}
while (st.empty() == false)
{
top = st.top();
st.pop();
toparea = hist[top] * (st.empty() ? i :
i - st.top() - 1);
if (largest_area < toparea)
largest_area = toparea;
}
return largest_area;
}
int main()
{
int hist[] = {6,7,4,5,3,2};
int n = sizeof(hist)/sizeof(hist[0]);
cout << "Largest area is " << getArea(hist, n);
return 0;
}실행 결과
Largest area is 16
예제에서 사용한 히스토그램은 {6, 7, 4, 5, 3, 2}입니다. 높이가 4인 막대(인덱스 2)를 기준으로 왼쪽의 높이 6, 7 막대까지 확장하면 너비 4, 높이 4인 직사각형이 만들어지고, 그 넓이는 4 × 4 = 16으로 이 히스토그램에서 가장 큰 값이 됩니다.