[백준 BOJ][stack] 6549 히스토그램에서 가장 큰 직사각형

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

링크

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

 

풀이

 

이 문제는 스택을 이용해서 풀 수 있는 문제입니다. 각 칸에서 왼쪽과 오른쪽으로 각각 어느 칸까지 뻗어 나갈 수 있는지 구하고, 그 길이 * 높이를 곱해서 가장 큰 크기를 선택하면 답이 나오고, 시간 복잡도는 3n, O(n)이 됩니다.

 

왼쪽으로 뻗어 나갈 수 있는 정도를 구하는 방법은 0번지부터 n-1번지까지 스택에 오름차순 정렬을 하는 것인데요. 높이가 같을 때도 스택에서 pop 해줘야 합니다.

그렇게 되면 스택 안에 있는 번지들은 i번째(현재 고려하는 칸)에서 왼쪽으로 뻗어 나갔을 때, 만나게 되는 장애물들을 나타내게 됩니다. i번째의 높이가 스택의 top번째의 높이보다 높다면 왼쪽으로 뻗을 때 바로 만나겠죠? 그럼 left[i]는 top이 됩니다. 그리고 i를 push하죠.

i번째의 높이가 같거나 작다면 왼쪽 칸들을 뚫고 지나갈 것입니다. 쭉 pop하다가 i번째의 높이가 top보다 커지면 그때 걸린다는 뜻이므로 left[i]는 top이 됩니다.

만약 스택이 empty가 된다면 장애물을 만나지 않는다는 것이므로 left[i]는 -1이 되고, i를 push합니다.

 

오른쪽으로 뻗을 수 있는 정도를 구하는 방법은 n-1에서 0까지 같은 방식으로 오름차순 정렬을 하고 스택이 empty가 될 때 장애물을 만나지 않는다는 것이므로 right[i]에 n을 저장해줍니다.

 

그렇게 left와 right를 구하면,

 

 

right[i] – left[i] -1을 해주면 가로 길이가 나오고 거기에 h[i]를 곱해주면 직사각형의 넓이를 구할 수 있으니 최댓값을 출력해주면 됩니다.

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

//6549_히스토그램에서 가장 큰 직사각형 #include <cstdio> #include <stack> #include <algorithm> #include <string.h> using namespace std;   int n; int h[100001], left[100001], right[100001];   stack<int> stk;     int main() {     while (true) {         scanf("%d", &n);           if (n == 0) break;           long long int ans = 0;         memset(h, 0, sizeof(h));           for (int i = 0; i < n; ++i) {             scanf("%d", &h[i]);         }           for (int i = 0; i < n; ++i) {    //왼쪽으로 뻗을 수 있는 정도             int tmp;               while (true) {                 if (!stk.empty()) {                     tmp = h[stk.top()];                 }                 else {                     tmp = -1;                 }                   if (tmp >= h[i]) stk.pop();                 else {                     if (stk.size() == 0) {                         left[i] = -1;                         stk.push(i);                         break;                     }                     else {                         left[i] = stk.top();                         stk.push(i);                         break;                     }                 }             }         }         while (!stk.empty()) stk.pop();           for (int i = n - 1; i >= 0; --i) {    //오른쪽으로 뻗을 수 있는 정도             int tmp;               while (true) {                 if (!stk.empty()) {                     tmp = h[stk.top()];                 }                 else {                     tmp = -1;                 }                   if (tmp >= h[i]) stk.pop();                 else {                     if (stk.size() == 0) {                         right[i] = n;                         stk.push(i);                         break;                     }                     else {                         right[i] = stk.top();                         stk.push(i);                         break;                     }                 }             }         }         while (!stk.empty()) stk.pop();           /*for(int i=0 ;i < n; ++i) printf("%d ", left[i]);         printf("\n");         for(int i=0 ;i < n; ++i) printf("%d ", right[i]);         printf("\n");*/             for (int i = 0; i < n; ++i) {    //넓이 구하기             long long int width;             width = right[i] - left[i] - 1;             ans = max(ans, width*h[i]);         }           printf("%lld\n", ans);     }       return 0; } Colored by Color Scripter

cs