[백준알고리즘] 6549번: 히스토그램에서 가장 큰 직사각형-C++

6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net)

6549번: 히스토그램에서 가장 큰 직사각형

보니까 2년 전에 풀다가 말았던 문제인 것 같다. 파이썬으로 풀려고 시도했던 흔적이 남아있다.

플레티넘 5라고 해서 너무 쉬운 방법은 안 풀릴 거 같았다. 조금 생각해서 스택을 이용해 푸는 방법을 생각했고, 약간 지저분해 보여 조금 아이디어를 가다듬고 문제를 풀었다. 사실 바로 풀릴지 모르고 했는데 돼서 놀랬다.

해당 문제에 대한 게시판에 반례 모음집도 만들어주신 분이 계셔서 틀렸습니다에 대한 반례도 쉽게 찾을 수 있었다.

---

문제 풀이

문제에 대한 아이디어는 나름 간단했다. 주어진 히스토그램에서 높이를 순차적으로 확인하면서, 직전 높이보다 낮은 높이가 주어지면, 이때까지의 히스토그램의 가장 큰 넓이를 구하도록 했다.

 

직전 높이보다 높은 높이가 주어지면, 그대로 스택에 push_back() 해주었다. 어차피 현재 입력될 블럭의 높이로 이전 입력되어있던 블록과 합쳐서 넓이를 구할 수 없기 때문이다.

그래서 현재 입력될 블럭의 높이가 직전 입력된 블록의 높이보다 작다면, 현재 입력된 블록의 높이로 구할 수 있는 넓이를 구했다.

 

즉, 현재 입력된 블럭을 포함해, 현재 입력된 블록의 높이로, 이전 왼쪽에 쌓여있는 히스토그램 블록들을 이용해, 최대한 큰 넓이를 구하도록 한 것이다.

 

그리고 마지막 히스토그램의 높이를 본 뒤에는 스택에 쌓여있는 높이들을 이용해 최종적으로 넓이를 구했다.

 

이 방법으로 문제를 풀 수 있었는데, 한 가지 논리를 놓친 부분이 있었다. 1 4 3 3 높이의 히스토그램이 주어졌을 때였다. 4가 pop_back()되고 3이 push_back() 될 때 index가 4가 있던 1이 되어야 하는데 그대로 2로 들어갔다. 높이가 4일 때도 높이가 3인 히스토그램과 높이를 맞출 수 있어야 하는데, 그 부분을 놓쳤었다.

반례 모음 만들어주신 분께 압도적 감사를 전합니다...

 

아래 소스코드에서는 스택에 넣을 때 인덱스와 높이를 같이 넣어주도록 했다. 처음에는 인덱스 없이 높이만 있는 스택으로 아이디어를 떠올렸었는데, 그럴 경우 pop한 개수만큼 push를 해주어야 하는 등 불필요한 작업들이 너무 많아지고 아이디어도 난잡해보였다. 그래서 최종적으로는 인덱스도 같이 넣어주면서 인덱스를 이용해 너비를 구해 쉽게 넓이를 구할 수 있도록 했다.

#include <cstdio>
#include <list>

struct StackElement_st {
	int iIndex;
	int iHeight;
};

int inputWidth();
std::list<int> inputHistogram(const int iWidth);
unsigned long long getBiggestRectangle(const std::list<int> &lstHistogram);
unsigned long long calculateArea(std::list<StackElement_st> &stack, const StackElement_st &seTarget);
void printArea(const unsigned long long ullArea);

int main(void) {
	while ( true ) {
		const int iWidth = inputWidth();
		if ( 0 == iWidth ) {
			break;
		}

		std::list<int> lstHistogram = inputHistogram(iWidth);
		const unsigned long long ullArea = getBiggestRectangle(lstHistogram);
		printArea(ullArea);
	}

	return 0;
}

int inputWidth() {
	int iWidth = 0;
	scanf("%d", &iWidth);
	return iWidth;
}

std::list<int> inputHistogram(const int iWidth) {
	std::list<int> lstHistogram;
	for ( int iCount = 0; iCount < iWidth; ++iCount ) {
		int iHeight = 0;
		scanf("%d", &iHeight);
		lstHistogram.push_back(iHeight);
	}
	return lstHistogram;
}

unsigned long long getBiggestRectangle(const std::list<int> &lstHistogram) {
	std::list<StackElement_st> stack;

	unsigned long long ullLargestArea = 0;

	// 하나씩 높이를 입력할 때 넓이 구하기
	int iIndex = 0;
	for ( std::list<int>::const_iterator itHeight = lstHistogram.begin(); itHeight != lstHistogram.end(); ++itHeight, ++iIndex ) {
		if ( true == stack.empty() ) {
			stack.emplace_back(StackElement_st { 0, *itHeight });
			continue;
		}

		if ( stack.back().iHeight < *itHeight ) {
			stack.emplace_back(StackElement_st { iIndex, *itHeight });
			continue;
		}
		else {
			unsigned long long ullArea = calculateArea(stack, StackElement_st { iIndex, *itHeight });
			ullLargestArea = (ullLargestArea < ullArea) ? ullArea : ullLargestArea;
		}
	}

	// 스택에 남아있는 정보로 넓이 구하기
	int iWidth = (int) lstHistogram.size();
	unsigned long long ullArea = calculateArea(stack, StackElement_st { iWidth, 0 });
	ullLargestArea = (ullLargestArea < ullArea) ? ullArea : ullLargestArea;

	return ullLargestArea;
}

unsigned long long calculateArea(std::list<StackElement_st> &stack, const StackElement_st &seTarget) {
	unsigned long long ullLargestArea = 0;
	int iLeftIndex = seTarget.iIndex;

	while ( false == stack.empty() ) {
		StackElement_st &seNearest = stack.back();
		if ( seNearest.iHeight <= seTarget.iHeight ) {
			break;
		}

		unsigned long long ullArea = (unsigned long long) seNearest.iHeight * (seTarget.iIndex - seNearest.iIndex);
		ullLargestArea = (ullLargestArea < ullArea) ? ullArea : ullLargestArea;
		
		iLeftIndex = seNearest.iIndex;

		stack.pop_back();
	}

	if ( true == stack.empty() ) {
		stack.emplace_back(StackElement_st { 0, seTarget.iHeight });
	}
	else {
		stack.emplace_back(StackElement_st { iLeftIndex, seTarget.iHeight });
	}

	return ullLargestArea;
}

void printArea(const unsigned long long ullArea) {
	printf("%llu\n", ullArea);
}