[백준] 1725 히스토그램 (Python)

1725번: 히스토그램

문제

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

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 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

 

---

문제 설명

 

높이의 배열을 받아 가장 큰 직사각형의 넓이를 구하는 문제

---

문제 풀이

 

가장 큰 직사각형을 구하기 위해서 다음과 같이 생각했다.

 

n번째 높이로 만들 수 있는 가장 큰 직사각형 넓이 = n번째 높이 * 연속되는 높이 중 n보다 크거나 같은 높이의 개수

 

그러나 이 문제의 입력이 십만이므로 O(Nlog(n)) 시간복잡도 내로 해결해야 한다.

 

그러기 위해 스택을 이용하였는데, 이전에 풀이하던 방법처럼 이전보다 작은 높이(a)가 입력으로 들어올 경우 이전의 입력 중 a보다 큰 높이들을 제거하게 되면 제거된 만큼의 길이를 알 수가 없어지게 된다.

 

이를 해결하기 위해 스택에서 제거할 때 제거된 위치를 저장했다가 스택에 추가할 때 해당 위치를 같이 저장하게 했다.

 

이렇게 하게 되면 해당 높이보다 크거나 같은 높이들의 가장 왼쪽 위치를 알 수 있게 되어, 만들 수 있는 가장 큰 넓이의 길이 부분을 구할 수 있게 된다.

 

또한 마지막에 높이 0을 추가하여 모든 높이가 스택에서 빠져나올 수 있게 했다.

---

 

코드

 

# 문제는 시작 지점보다 낮은 높이의 길다란 직사각형

import sys
input = sys.stdin.readline
N = int(input())
histogram = [int(input()) for _ in range(N)] + [0] #stack의 남아있는 원소가 없도록
max_size = 0
c = 0
stack = []

for i in range(N+1):
    c = i	#pop이 이루어 지지 않을 경우 언제(시작지점) 추가됐는지를 위한 초기화
    while stack and stack[-1][0] > histogram[i]:
        h, old_c = stack.pop()
        if h * (i-old_c) >= max_size:	#i-old_c = 해당 높이의 가장 긴 길이
            max_size = h * (i-old_c)
        c = old_c	#while문이 반복되면서 해당 높이보다 큰거나 같은 높이 중 가장 왼쪽의 위치를 저장하게 됨

    stack.append([histogram[i], c])

print(max_size)

---