[Algorithm] C++/Python 백준 6549번 : 히스토그램에서 가장 큰 직사각형

 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

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    while (true) {
        int n;
        cin >> n; // 히스토그램의 막대 수 입력
        if (n == 0) break; // 입력의 끝이면 종료

        vector<long long> heights(n); // 막대의 높이를 저장할 벡터
        for (int i = 0; i < n; ++i) {
            cin >> heights[i]; // 각 막대의 높이 입력
        }

        stack<int> s; // 인덱스를 저장할 스택
        long long max_area = 0; // 최대 넓이 초기화

        for (int i = 0; i < n; ++i) {
            // 현재 막대의 높이가 스택 최상단 막대보다 작을 때까지 반복
            while (!s.empty() && heights[s.top()] > heights[i]) {
                int tp = s.top(); // 스택 최상단 막대의 인덱스
                s.pop(); // 스택에서 제거
                long long h = heights[tp]; // 스택 최상단 막대의 높이
                long long width = s.empty() ? i : i - s.top() - 1; // 너비 계산
                max_area = max(max_area, h * width); // 최대 넓이 갱신
            }
            s.push(i); // 현재 막대의 인덱스를 스택에 추가
        }

        // 스택에 남은 막대 처리
        while (!s.empty()) {
            int tp = s.top();
            s.pop();
            long long h = heights[tp];
            long long width = s.empty() ? n : n - s.top() - 1;
            max_area = max(max_area, h * width);
        }

        cout << max_area << '\n'; // 최대 넓이 출력
    }
    return 0;
}

 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

#include <stdio.h>
#include <malloc.h>

int main() {
    while (1) {
        int n;
        scanf("%d", &n); // 히스토그램의 막대 수 입력
        if (n == 0) break; // 입력의 끝이면 종료

        long long* heights = (long long*)malloc(n * sizeof(long long)); // 막대 높이 배열 동적 할당
        int* stack = (int*)malloc(n * sizeof(int)); // 스택 배열 동적 할당
        int top = -1; // 스택의 최상단 인덱스

        for (int i = 0; i < n; ++i) {
            scanf("%lld", &heights[i]); // 각 막대의 높이 입력
        }

        long long max_area = 0; // 최대 넓이 초기화
        int i = 0;
        while (i < n) {
            // 스택이 비어 있거나 현재 막대의 높이가 스택 최상단 막대보다 크거나 같으면
            if (top == -1 || heights[stack[top]] <= heights[i]) {
                stack[++top] = i++; // 현재 막대의 인덱스를 스택에 추가
            } else {
                int tp = stack[top--]; // 스택에서 최상단 막대 인덱스 꺼내기
                long long h = heights[tp]; // 높이
                long long width = top == -1 ? i : i - stack[top] - 1; // 너비 계산
                long long area = h * width; // 넓이 계산
                if (area > max_area) max_area = area; // 최대 넓이 갱신
            }
        }

        // 남은 스택 처리
        while (top != -1) {
            int tp = stack[top--];
            long long h = heights[tp];
            long long width = top == -1 ? i : i - stack[top] - 1;
            long long area = h * width;
            if (area > max_area) max_area = area;
        }

        printf("%lld\n", max_area); // 최대 넓이 출력

        free(heights); // 동적 할당 메모리 해제
        free(stack);
    }
    return 0;
}

 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

import sys

input = sys.stdin.readline

while True:
    inputs = sys.stdin.readline().split()
    n = int(inputs[0]) # 히스토그램의 막대 수
    if n == 0:
        break # 입력의 끝이면 종료
    heights = list(map(int, inputs[1:])) # 막대 높이 리스트

    stack = [] # 인덱스를 저장할 스택
    max_area = 0 # 최대 넓이 초기화
    i = 0
    while i < n:
        # 스택이 비어 있거나 현재 막대의 높이가 스택 최상단 막대보다 크거나 같으면
        if not stack or heights[stack[-1]] <= heights[i]:
            stack.append(i) # 현재 막대의 인덱스를 스택에 추가
            i += 1
        else:
            tp = stack.pop() # 스택에서 최상단 막대 인덱스 꺼내기
            h = heights[tp] # 높이
            width = i if not stack else i - stack[-1] - 1 # 너비 계산
            area = h * width # 넓이 계산
            if area > max_area:
                max_area = area # 최대 넓이 갱신

    # 남은 스택 처리
    while stack:
        tp = stack.pop()
        h = heights[tp]
        width = i if not stack else i - stack[-1] - 1
        area = h * width
        if area > max_area:
            max_area = area

    print(max_area) # 최대 넓이 출력