문제 출처

1. 문제설명

  • 히스토그램의 높이가 주어진다.
  • 히스토그램에서 가장 넓이가 큰 직사각형의 구하라



2. 알고리즘 설계

  • 자료구조 스택 문제이다.

  • 입력받은 높이(h)와 그에 해당하는 인덱스(idx)를 활용해야 한다.

  • 알고리즘
    • n개의 높이를 순차적으로 입력받는다.
    • 스택에 저장되어 있는 h가 현재 입력받은 h보다 크거나 같으면,
      • (현재의 idx - top().idx) * top.h
        • 스택에 저장된 값이 더 작기 때문에 더 작은 높이로 사각형을 계산해야 한다.
      • idx를 top().idx로 변경
      • pop()
    • n개를 모두 입력받고, 스택이 비어있지 않은 경우,
      • 모든 사각형을 계산하지 않았다는 의미
      • 또한, 스택에는 값이 오름차순으로 쌓여 있게 된다.
        • 그렇지 않다면, 이전 단계의 조건에서 처리되었기 때문이다.
      • 예를 들어, [6,7,8,9]가 있다고 해보자.
        • 가장 큰 사각형은 6*4=24 이다.
        • 스택이 비어있을 때까지, 즉, 6을 만날 때까지
        • 정답과 (n-idx) * h 중 큰 값으로 정답을 갱신하면 된다.



3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	while (true) {
		int n;
		cin >> n;

		if (n == 0) break;

		stack<pll> st;
		ll ans = 0;

		for (int i = 0; i < n; i++) {
			int h, idx = i;
			cin >> h;

			while (!st.empty() && st.top().first >= h) {
				ans = max(ans, (i - st.top().second) * st.top().first);
				idx = st.top().second;
				st.pop();
			}
			st.push({ h, idx });
		}

		while (!st.empty()) {
			ans = max(ans, (n - st.top().second) * st.top().first);
			st.pop();
		}
		cout << ans << '\n';
	}

	return 0;
}



4. 소감

  • 입력받는 h가 큰 값이라서, 더하다보면 int 범위를 넘어설 수 있다.
  • ans만 long long형으로 선언할 수도 있지만,
    • (long long)1을 곱해줘야 한다.
    • 깔끔한 코드를 위해 전부 long long형으로 선언해주었다.



5. 참고

  • 이전 게시글까지는 2. 알고리즘 설계, 3. 로직 으로 구성했는데,
  • 생각해보니 두 가지가 같은 거라서 하나로 통합했다.
  • 앞으로는 현재 게시글 양식을 쓸 예정이다.