Gidhub BE Developer

# [BOJ] 1725. 히스토그램

2018-09-14
goodGid

## Problem

Problem URL : 히스토그램

## [1] Answer Code (18. 09. 14)

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

int main() {
int n,value;
scanf("%d", &n);

stack<pair<int, int>> s;
long long sum=0;
long long tmpSum;
long long tmpX;

for (int i = 1; i <= n; i++) {
scanf("%d", &value);
tmpX = i;

while (!s.empty() && s.top().second >= value){
tmpSum = (i - s.top().first) * s.top().second;
sum = sum < tmpSum ? tmpSum : sum;
tmpX = s.top().first;
s.pop();
}

s.push(make_pair(tmpX, value));
}

while (! s.empty()){
tmpSum = (n+1 - s.top().first) * s.top().second;
sum = sum < tmpSum ? tmpSum : sum;
s.pop();
}
printf("%lld\n", sum);
}
``````

### Review

• Stack을 사용한 히스토그램 문제 풀이

## [2] Answer Code (18. 09. 14)

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

/*
st is stack
sp is stack point
*/
int st[100001];
int sp;

int a[100001];
int n;

int main(){
cin.tie(0);
ios::sync_with_stdio();

scanf("%d", &n);
for(int i = 1; i <=n ;i++)
scanf("%d", a+i);

int ans = 0;
for(int i = 1; i <= n; i++){
int left, right;
while(sp > 0 && a[st[sp-1]] >= a[i]){
int height = a[st[sp-1]];
sp--; // pop()과 같은 역할이다.

if(sp == 0)
left = 1;
else
left = st[sp-1] + 1;

right = i-1;
int width = ( right-left+1 ) * height;
if(ans < width)
ans = width;
}
st[sp] = i;
sp++; // push()와 같은 역할이다.
}

while(sp > 0){
int left, right;
int height = a[st[sp-1]];
sp--;

if(sp == 0) left = 1;
else left = st[sp-1] + 1;

right = n;
int width = ( right-left+1 ) * height;
if(ans < width)
ans = width;
}

printf("%d\n", ans);
return 0;
}
``````

### Review

• stack 구현없이 배열을 stack처럼 사용한 풀이.

## [3] Answer Code (18. 09. 14)

``````#include <iostream>
using namespace std;
long long hist[100000];

int stack[10001];
int top = -1;

void push(int x){
stack[++top] = x;
}

int empty() {
if( top < 0 )
return 1;
else
return 0;
}

void pop() {
if (empty() == 1){ }
else {
stack[top--] = 0;
}
}

void size(){
cout << top + 1 << "\n";
}

int main(){
int n;

long long max = -1;
scanf("%d", &n);

for (int i = 0; i < n; i++){
scanf("%lld", &hist[i]);
while (!empty() && hist[stack[top]] > hist[i]){
int j = stack[top];
pop();
long long width = i;

if (!empty())
width -= stack[top] + 1; // width = width - ( stack[top] + 1 ) 이다.
long long cmp = hist[j] * width;
max = max < cmp ? cmp : max;
}
push(i);
}

while (!empty()) {
int j = stack[top];
pop();
long long width = n;
if (!empty())
width -= stack[top] + 1;
long long cmp = hist[j] * width;
max = max < cmp ? cmp : max;
}

printf("%llu\n", max);

return 0;
}
``````

### Review

• stack을 구현해서 stack을 사용해서 PS 진행

## [4] Answer Code (18. 09. 24)

``````#include <cstdio>
#include <stack>
using namespace std;
int a[100000];
int main() {
int n;
scanf("%d",&n);
for (int i=0; i<n; i++) {
scanf("%d",&a[i]);
}
stack<int> s;
int ans = 0;
for (int i=0; i<n; i++) {
int left = i;
while(!s.empty() && a[s.top()] > a[i]) {
int height = a[s.top()];
s.pop();
int width = i;
if (!s.empty()) {
width = (i - s.top() - 1);
}
if (ans < width*height) {
ans = width*height;
}
}
s.push(i);
}
while(!s.empty()) {
int height = a[s.top()];
s.pop();
int width = n;
if (!s.empty()) {
width = n-s.top()-1;
}
if (ans < width*height) {
ans = width*height;
}
}
printf("%d\n",ans);
return 0;
}
``````