BOJ #1725 히스토그램

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

---

소스코드(C언어)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(a, b) ((a > b) ? (a) : (b))

typedef struct {
	int height;
	int num;
	struct NODE* next;
}NODE;

typedef struct {
	int size;
	struct NODE* top;
}STACK;

void push(STACK* stack, int h, int n);
int top(STACK* stack);
int pop(STACK* stack, int *h, int *n); //pop 하면 1, 못하면 0 출력

int main() {
	int N, h, S = 0, tmp, num = 1;
	scanf("%d", &N);

	STACK* stack;
	stack = (STACK*)malloc(sizeof(STACK));
	stack->size = 0;
	stack->top = NULL;

	scanf("%d", &tmp);
	for (int i = 1; i < N; i++) { //tmp는 이전 높이, h는 현재 높이
		scanf("%d", &h);

		if (h == tmp)
			num++;
		else if (h < tmp) {
			S = max(S, tmp*num);

			while (top(stack) >= h && pop(stack, &tmp, &num))
				S = max(S, tmp*num);

			tmp = h;
			num++;
		}
		else { //h > tmp
			push(stack, tmp, num);
			tmp = h;
			num = 1;
		}
	}

	S = max(S, tmp*num);
	while (pop(stack, &tmp, &num))
		S = max(S, tmp*num);

	printf("%d\n", S);

	while (stack->size) {
		pop(stack, &h, &num);
	}
	free(stack);

	return 0;
}

void push(STACK* stack, int h, int n) {
	NODE* node;
	node = (NODE*)malloc(sizeof(NODE));
	node->height = h;
	node->num = n;
	node->next = stack->top;
	stack->top = node;
	stack->size++;
}

int top(STACK* stack) {
	if (stack->size == 0)
		return -1;
	NODE* tmp = stack->top;
	return tmp->height;
}

int pop(STACK* stack, int *h, int *n) { //pop 하면 1, 못하면 0 출력
	if (stack->size == 0)
		return 0;
	
	NODE* tmp;
	tmp = stack->top;
	*h = tmp->height;
	*n += tmp->num;
	stack->top = tmp->next;
	free(tmp);
	stack->size--;
	return 1;
}

 

Idea

현재 높이와 이전 높이를 비교하여 넓이를 계산한다.

여기서 주의할 점은, for문이 끝나고 스택안에 남아있는 블록들을 고려해주어야 한다.