문제 링크

<aside> 💡 자료 구조/분할 정복/세그먼트 트리/스택

</aside>

Memory 125604KB Time 156ms Code Length 415B

n = int(input().strip())
heights = list(map(int, input().strip().split()))
stack = []
ans = 0
for i in range(n):
    while stack and heights[stack[-1]] > heights[i]:
        h = heights[stack.pop()]
        w = i if not stack else i-stack[-1]-1
        ans = max(ans, h * w)
    stack.append(i)
while stack:
    h = heights[stack.pop()]
    w = n if not stack else n-stack[-1]-1
    ans = max(ans, h * w)
print(ans)

이 코드는 주어진 높이 배열을 통해 만들 수 있는 최대 직사각형의 넓이를 찾는 알고리즘이다.

처음에 사용자로부터 직사각형의 개수를 입력받고, 각각의 높이를 입력받는다. 그 후 빈 스택과 결과값을 초기화한다.

다음으로, 각 직사각형에 대해 스택에 저장된 마지막 직사각형의 높이와 현재 직사각형의 높이를 비교한다. 만약 스택에 저장된 직사각형의 높이가 현재 직사각형의 높이보다 크다면, 스택에서 직사각형을 제거하고 그 직사각형의 높이와 너비를 계산하여 최대 넓이를 갱신한다.

이 과정을 모든 직사각형에 대해 반복한 후, 스택에 남아있는 직사각형에 대해 같은 과정을 수행한다. 이때 너비는 전체 직사각형의 개수에서 스택에 남아있는 마지막 직사각형의 위치를 뺀 값이다.

마지막으로 계산된 최대 넓이를 출력한다.