[백준] 1725. 히스토그램(python, 파이썬)

문제

1725. 히스토그램

📌 아이디어

스택 자료 구조를 사용해 문제에 접근했습니다.

1. 첫번째 막대 그래프부터 탐색하며 스택에 막대 그래프의 위치와 높이 두 정보를 push합니다.
2. 막대 탐색시 스택에 값이 존재한다면 현재 막대 높이보다 큰 막대를 만날때까지 pop합니다.
3. pop한 막대의 인덱스와 현재 인덱스의 차이는 밑변이기에 높이와 곱해 최대 넓이를 갱신합니다.

❗️ 추가적으로 전체가 동일한 높이일 경우를 꼭 고려해야합니다! 전체 탐색 후 재탐색을 통해 최대 넓이를 갱신해야 이 문제를 해결할 수 있습니다.

📌 코드

import sys
input = sys.stdin.readline

N = int(input())
lst = []
for _ in range(N):
    num = int(input())
    lst.append(num)

stack = []
max_v = 0
for i in range(N):
    idx = i
    # 스택에 값이 존재하면 큰 값을 만날 때까지 pop
    while stack and stack[-1][1] > lst[i]:
        idx, height = stack.pop()
        # 현재 안덱스와 해당인덱스까지의 차이와 높이를 곱해서 최대 넓이를 탐색
        rst = (i - idx) * height
        max_v = max(max_v, rst)
    stack.append([idx, lst[i]])

# 전체가 동일한 높이일 경우를 추가적으로 고려
while stack:
    idx, height = stack.pop()
    rst = (N - idx) * height
    max_v = max(max_v, rst)

print(max_v)

피드백 및 개선점은 댓글을 통해 알려주세요😊