백준 - 1725. 히스토그램

[백준] 1725. 히스토그램

Link 플레 5티어 문제

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

7
2
1
4
5
1
3
3

예제 출력 1

8

풀이

풀다가 결국 갈피를 잡지못하고 문제 유형만 컨닝하려고 하였으나, 최종 제출에서 계속 실패하여 결국 답을 찾아본 문제..

Stack에 순서대로 성분들을 넣는데, stack의 마지막, 그러니까 stack 제일 위의 성분이 이번 height보다 더 크다면 stack에서 pop을 한다면, 결과적으로 stack에는 높이 순서대로 성분이 저장되게 된다.

예제입력을 예로 들면..

1. stack = [[0, 2]
2. stack = [[1,1]] –> 2가 1보다 더 크니까 pop하고 stack에 1을 append
3. stack = [[1,1], [2,4]] –> 1이 4보다 작으니까 그대로 append
4. stack = [[1,1], [2,4], [3,5]] –> 4가 5보다 작으니까 그대로 append
5. stack = [[1,1]] –> 1이 4와 4보다 작으니까 이들을 pop
6. stack = [[1,1], [4,1]] –> 1은 서로 같으니까 append
7. stack = [[1,1], [4,1], [5,3]] –> 1이 3보다 작으니까 append
8. stack = [[1,1], [4,1], [5,3]. [6,3]] –> 1이 3보다 작으니까 append

• 이런식으로 stack에 append와 pop을 하면서 stack에서 성분이 pop될 때마다 해당 pop된 height를 높이로,
• 그때의 인덱스와 현 인덱스의 차이에 마이너스 1을 한 것을 width로 두고,
• 서로 곱하여 area를 구하고,
• max함수로 max_area를 업데이트 한다

라는 순서로 코딩을 하면 된다. 아래는 내가 작성한 코드이다.

n = int(input())
heights = []
for _ in range(n):
    heights.append(int(input()))

stack = []
max_area = 0
width = 0

for i, h in enumerate(heights):
    while stack and stack[-1][1] > h:
        idx, value = stack.pop()
        if stack:
            width = i - stack[-1][0] - 1
        else:
            width = i
        max_area = max(max_area, width * value)

    stack.append([i, h])


width = 0
while stack:
    idx, value = stack.pop()
    if stack:
        width = n - stack[-1][0] - 1
    else:
        width = n
    max_area = max(max_area, width * value)

print(max_area)