[BOJ] 1725 - 히스토그램 (Python)

 

 

아이디어

 

스택을 이용하여 각 위치에서 해당 직사각형의 높이로 만들 수 있는 가장 큰 직사각형 넓이를 구해 나간다.

 

 

풀이

 

6549번 히스토그램에서 가장 큰 직사각형에서 스택을 이용한 풀이 #2와 같다.

 

첫 번째 수는 N, 직사각형의 높이들은 sys.stdin.readlines로 H에 입력 받고, H 끝에는 0을 추가한다.

 

직사각형의 넓이를 구하기 위해 필요한 직사각형의 위치들을 스택 stack에 저장하고,

이 위치로 직사각형 양쪽 끝과 H에서 해당 직사각형의 높이를 알 수 있어 각 위치에서의 직사각형의 면적을 구할 수 있다.

 

for문에서는 차례로 직사각형 높이가 증가하면 그 위치를 스택에 넣고 감소하면 스택에서 위치를 꺼내 그 넓이를 계산한다.

위치 i의 직사각형 높이가 stack[-1] 위치의 직사각형 높이보다 작다면

stack[-1] 위치의 가장 넓은 직사각형의 오른쪽 끝은 위치 i-1이 되고, 왼쪽 끝은 stack[-2]+1이 된다.

 

stack에 초기값으로 -1을 넣어두고, for문에서 처음 i가 0일 때는 while문이 실행되지 않으므로 stack에 0이 추가된다.

스택에는 직사각형의 높이가 증가하는 형태로 그 위치들이 저장되는데,

H 끝에 0을 추가하여 for문에서 i가 N일 때 스택에 남아 있는 위치의 직사각형 넓이들을 계산하도록 한다.

 

import sys

def solution():
    N = int(input())
    H = list(map(int, sys.stdin.readlines()))+[0]
    res = 0
    stack = [-1]
    for i in range(N+1):
        while stack and H[i] < H[stack[-1]]:
            idx = stack.pop()
            l = stack[-1]
            res = max(res, H[idx]*(i-(l+1)))
        stack.append(i)
    print(res)

solution()