백준 1725 : 히스토그램

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

1725번: 히스토그램

 

유명한 히스토그램 문제다. 아래 블로그를 보고 배웠다. 아래 블로그에 아주 설명이 잘 되어있으니 참고하도록 하자.

 

https://jaimemin.tistory.com/827

백준 1725번 히스토그램

 

내 나름대로 위의 블로그를 보면서 공부한 내용을 정리하자면 다음과 같다.

 

히스토그램 문제에서 핵심은 i번째 인덱스의 높이 값보다 좌우의 막대의 높이가 더 높다면, 현재 인덱스의 높이값을 기준으로 사각형을 만들수 있다는 것이다.

좌우로 직접 검사하기에는 시간복잡도가 문제가 되니, 스택에 오름차순으로 막대를 정렬하여 오른쪽만 비교하는게 이 문제 해결을 위한 아이디어다.

여기서 정렬이라 함은 막대의 위치를 직접 움직여서 정렬하겠다는 뜻이 아니다.

아래 그림 처럼 영역(그림에서 색깔로 표현)별로 나누어서 스택에 오름차순으로 들어가있도록 로직을 수행한다는 뜻이다.

 

그러면 이런 의문점이 들 수 있다.

'그러면 왼쪽으로 확장해야되는 상황에는 어떻게 해요?'

물론 그런 상황이 발생할 수 있다. 이 로직에서는 스택이 비어있을 경우 너비 값을 현재 인덱스 위치 값으로 줌으로써 위와 같은 케이스까지 커버한다.

 

코드를 보기 전까지는 무슨 말인지 이해가 잘 되지 않을 수도 있다. 나도 코드가 이해가 잘 되지 않아 여러가지 경우를 코드를 따라가면서 직접 손으로 그려봤다. 직접 코드를 보면서 한 번 로직을 따라가 보자.

#include <iostream>
#include <vector>
#include <stack>

#define max(a,b) a>b?a:b
using namespace std;

void solution() {
	int n, tmp;
	int target, width, max_val = 0;
	vector<int> height;
	stack<int> left;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tmp, height.push_back(tmp);
	}
	//현재 높이 값이 스택의 제일 위에 있는 인덱스의 높이 값보다 작을 때
	//넓이를 구하는 로직으로 진입하므로 제일 마지막에 높이 0 추가
	height.push_back(0);

	for (int i = 0; i < height.size(); i++) {
		//left에는 높이가 오름차순인 순서대로 삽입되고 현재 높이가
		//left의 제일 위의 인덱스의 높이 값보다 작거나 같을 시
		//오름차순이 아니므로 스택에서 꺼내 넓이 구해줌
		while (!left.empty() && height[left.top()] >= height[i]) {
			//높이 값을 사용하고자 하는 타겟 idx를 스택에서 꺼냄
			target = left.top();
			left.pop();

			//만약 left가 비어있다면, i - 1까지의 높이들 중에서
			//현재 값인 i번째 높이가 제일 작다는 뜻이므로
			//시작부터 i번째 인덱스까지를 너비로 잡아 넓이 계산
			if (left.empty()) width = i;
			//left에 값이 있다면, left는 오름차순 정렬 되어있으므로
			//해당 위치에서 현재 위치 바로 전까지를 너비로 잡음
			else width = i - left.top() - 1;

			max_val = max(max_val, height[target] * width);
		}
		left.push(i);
	}

	cout << max_val;
}

int main(void) {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2924 kb

시간: 12 ms