개요

[링크] 백준 1725번: 히스토그램

• 입력
  첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

• 출력
  첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

접근 방식

[링크] 백준 2104(부분 배열 고르기)
문제와 유사해서 않고 비슷하게 풀었다.
차이점은 2104번은 해당 부분수열의 합을 계산해야하지만
이 문제는 밑변의 길이만 구하면 되서 더 편하다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<long long> v;							//각 네모 길이 저장하는 벡터

void input(int& amount) {							//입력값 받는 함수
	int temp = 0;
	cin >> amount;
	for (int i = 0; i < amount; i++) {
		cin >> temp;
		v.push_back(temp);
	}
}

long long solution(int lt,int rt) {					//재귀해서 가장 큰 사각형값 return하는 함수
	if (lt == rt) return v[lt];						//만약 범위같을땐 밑변1에 높이 lt인 사각형이므로 return v[lt]
	int mid = (lt + rt) / 2;						//중간값 
	int l = mid,r=mid+1;							//l은 중간값 r은 중간값 +1
		
	long long minH = min(v[l],v[r]);				//minH값은 최소 변길이. 

	long long ret = max(solution(lt, mid), solution(mid + 1, rt));	//재귀로 이전 값들의 최대 사각형넓이값 불러옴 

	ret = max(ret, (r - l+1) * minH);								//이미 지나온 재귀값들의 최대값과 지금 l, r값에 해당하는 사각형 넓이 값 비교 이 문장 안넣으면 답틀ㄹ림ㅇ
	while (lt < l || r < rt) {										//l이 lt값(경계값)보다 크고, r이 rt값(경계값)보다 작을 때
		if (r < rt && (l == lt || v[l - 1] < v[r + 1])) {			//오른쪽으로 진행할 때,
			r++;
			minH = min( v[r], minH);
		}
		else {														//왼쪽으로 진행할 때,
			l--;
			minH = min(v[l], minH);

		}
		ret = max(ret, (r - l+1) * minH);							//각각 진행할때마다 ret값 갱신
	}

	return ret;


	
}

int main() {
	int amount;
	input(amount);
	cout << solution(0, amount-1);
}

문풀후생

전반적으로 2104번과 비슷해서 좀 빠르게 풀렸던 것 같다.

stack을 이용한 풀이(10/28 추가)

이 방법으로는 못 풀어서 한번에 못 푼 문제 태그 추가했다.

접근 방법

1. 막대를 왼쪽에서 오른쪽으로 하나씩 탐색하면서
   스택이 비어있거나 이전 막대보다 길이가 길다면 해당 히스토그램 push,
   이전 막대보다 길이가 짧다면 stack안의 막대 중 해당 막대보다 긴 막대들을 다 pop하며 최대 넓이 구한다.

2. 첫 번째 실수는 index를 고려안했다.
   예를들어 7 1 4 6 3 5 8 2 이런식일때 1 4 6 push되고,
   3 push될차례에 4와 6 pop되고 5 8 push되고
   2 push 될 차례에 1 3 5 8중 3, 5 ,8 이 pop되면서 최대 넓이를 구해야하는데
   index를 고려안하고 단순히 길이만으로 구현해버리니 1과 3 사이의 index가 2만큼 떨어져있지만
   길이만 고려하면 index가 1만큼 차이나는 것으로 계산되어 오류가난다.
   -> stack에 넣을 막대를 높이값과 index값을 가진 구조체로 구현하여 해결하였다,

3. 두 번째 실수는 pop하는 과정에서 해당 막대중 최대 넓이를 구할때였다.

   넓이를 구하는 과정에서 막대를 pop할때 이번의 push하려는 막대와
   스택의 top에 위치한 막대와의 index차이만을 구하여 계산을 했다.

   위의 예시로 설명하자면 7 1 4 6 3 5 8 2 이렇게 있다면 2가 stack에 들어올 차례에
   스택 안에는 1 3 5 8 이렇게 있다.

   2가 들어왔을 때,
   8 막대가 가질 수 있는 최대 넓이는 8 * 1,
   5 막대가 가질 수 있는 최대 넓이는 5 * 2,
   3 막대가 가질 수 있는 최대 넓이는 3 * 3,
   1 막대가 가질 수 있는 최대 넓이는 1 * 4
   이런식으로 pop할 막대와 넣으려는 막대사이의 index 만 고려했지
   pop할 막대와 그 이전 막대의 index는 고려를 안하여 틀린것이다.

   -> s.to()p값을 저장해놓은 후 s.pop을 중간에 한번하여 이전 값과 비교하게 구현하였다,

   	while (!s.empty() && s.top().height>=inputArr[lastIndex]) {
   		//stack의 top값 저장
   		preIndex = s.top().index;
   		preHeight= s.top().height;
   		//pop을 하여 비교하려는 막대 이전 막대의 index구함
   		s.pop();
   
   		//pop했을때 스택이 비었다면 해당 막대가 제일 작은 막대이므로 시작점부터 lastindex까지가 거리
   		if (s.empty()) ret = max(ret, preHeight*lastIndex);
   		//스택이 안비었다면 pop한 막대로 만들수 있는 최대 넓이값의 가로길이는 이전 막대와 lastindex사이의 거리다.
   		else ret = max(ret, (long long)preHeight * (lastIndex - s.top().index-1));
   	}

코드

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

int N;
long long inputArr[100'001];

struct histogram {
	int index;
	int height;
};

stack<histogram> s;

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> inputArr[i];
	}
}

long long maxArea(int lastIndex) {
	long long preIndex = 0,preHeight=0, ret=0;
	//스택안의 값중 lastindex번째로 들어온 값보다 큰게 있다면
	while (!s.empty() && s.top().height>=inputArr[lastIndex]) {
		//stack의 top값 저장
		preIndex = s.top().index;
		preHeight= s.top().height;
		//pop을 하여 비교하려는 막대 이전 막대의 index구함
		s.pop();

		//pop했을때 스택이 비었다면 해당 막대가 제일 작은 막대이므로 시작점부터 lastindex까지가 거리
		if (s.empty()) ret = max(ret, preHeight*lastIndex);
		//스택이 안비었다면 pop한 막대로 만들수 있는 최대 넓이값의 가로길이는 이전 막대와 lastindex사이의 거리다.
		else ret = max(ret, (long long)preHeight * (lastIndex - s.top().index-1));
	}
	histogram h = { lastIndex, inputArr[lastIndex] };
	s.push(h);
	return ret;
}

void solution() {
	//이전 값,정답
	long long Ans=0;
	for (int i = 0; i < N; i++) {
		//이전 값이 없다면
		if (i == 0) {
			histogram h = {i, inputArr[i]};
			s.push(h);
		}
		//이전 값이 있다면
		else if(!s.empty()) {
			//이전값보다 입력값이 더 크면
			if (s.top().height<= inputArr[i]) {

				histogram h = {i, inputArr[i]};
				//스택에 푸시
				s.push(h);
			}
			//이전값보다 입력값이 더 작으면
			else {
				//해당 입력값까지의 제일 큰 값 넣어준다.
				Ans = max(Ans,maxArea(i));
			}
		}
	}
	//stack이 비어있지 않다면 0값을 넣어줘 남은 스택들끼리 연산하게 함.
	if (!s.empty()) {
		Ans = max(Ans, maxArea(N));

	}
	cout << Ans;
}

int main() {
	input();
	solution();
}

문풀후생

확실히 stack의 아이디어가 쉽지만 스택 안의 인덱스간의 거리 처리가 좀 까다로웠다.