[알고리즘][스택] 1725번 히스토그램 | baekjoon 문제 풀이

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

 

 

 

 

> 주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 문제이다.

간단한~ 문제라고 생각했는데, 처음에 스택을 이용해서 어떻게 풀어야 좋을지 감이 오지 않아서 풀이 방법을 찾아보고, 이해하면서 작성하였다.

 

 

 

풀이

해당 문제는 스택으로 풀거나 분할 정복을 이용해서 풀 수 있는데, 분할 정복은 아직 이해가 되지 않아서... 스택으로 해결하는 방법만 적어보려고 한다.

 

접근 방법은 아래와 같은데,

모든 높이값은 arr 배열에 순서대로 넣은 후,

stack에는 index 값을 넣고 이를 활용하여 넓이를 계산한다.

 

접근 방법을 코드로 구현하면 다음과 같다.

st.push(0);
for (int i = 1; i <= N + 1; i++)
    {
        while (!st.empty() && arr[st.top()] > arr[i])
        {
            int height = arr[st.top()];
            st.pop();
            int width = i - st.top() - 1;
            area = max(area, height * width);
        }
        st.push(i);
    }
}

 

---

 

해당 과정을 직접 그림으로 그려보았다.

예제의 N값은 6이며, 

편의를 위해 0 인덱스의 값은 arr[0]=0으로 두고 계산을 진행한 것이다.

 

# i = 1, 2, 3

-> 높이 값이 계속 증가하고 있기 때문에, stack에 계속 push해준다.

 

# i = 4

-> 높이 값이 감소하므로 이제 넓이 계산을 시작한다.

1) 우선 현재 stack에 있는 top값을 이용하여 arr[top] 값을 구한다. 이 값이 높이가 된다.

2) 그 후, stack에 있는 top값을 pop해준다.

3) 마지막으로 현재의 i값에 top값을 빼고 1도 빼서 가로 길이를 구한다.

(3번의 이유: 높이값이 계속 감소하므로,  i에 top값을 빼는 형태로 구현하여 최대 넓이를 구할 수 있도록 유도.)

 

 

top = 3일 때 / top = 2일 때의 면적

 

# i = 5, 6

-> 높이 값이 계속 증가하고 있기 때문에, stack에 계속 push해준다.

 

# i = 7

-> 높이 값이 감소하므로 넓이 계산을 시작한다.

우선 현재 stack에 있는 top값을 이용하여 arr[top] 값을 구한다. 이 값이 높이가 된다.

그 후, stack에 있는 top값을 pop해준다.

마지막으로 현재의 i값에 top값을 빼고 1도 빼서 가로 길이를 구한다.

(아까 stack에 있는 1 값은 pop하지 않았기 때문에, 지금 i=7일 때 계산에서 사용할 수 있음. 그래서, 가로 길이가 가장 넓어졌을 때의 최대 넓이를 구할 수 있다!)

 

top = 6일 때 / top = 5 / top = 4 / top = 1 일 때의 면적

 

 

전체 코드는 아래와 같다.

#include <iostream>
#include <stack>
using namespace std;

int arr[1000002]; 
// 히스토그램의 가로 칸의 수 <= 1,000,000  (+2: )
// 히스토그램의 높이 <= 1,000,000,000
//			int 범위 <= 2,147,483,647

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // C언어와 C++의 동기화를 끊어주는 코드
	
	int N, area = 0; // N: 히스토그램 가로 칸의 수 / area: 최대 넓이
	cin >> N; 
	stack<int> st;

    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    st.push(0);
    for (int i = 1; i <= N + 1; i++)
    {
        while (!st.empty() && arr[st.top()] > arr[i])
        {
            int height = arr[st.top()];
            st.pop();
            int width = i - st.top() - 1;
            area = max(area, height * width);
        }
        st.push(i);
    }
    cout << area;
}

 

시간과 메모리는 다음과 같이 소요되었다.