문제:
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.
히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.
입력:
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.
출력:
각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
while True:
n, *heights = map(int, input().split())
if n == 0:
break
stack = [] # 높이를 저장할 스택
max_area = 0 # 가장 큰 직사각형의 넓이
for i in range(n):
while stack and heights[i] < heights[stack[-1]]: # 스택이 있고, 다음 건물 높이가 스택 마지막 보다 낮을때까지
height = heights[stack.pop()] # 높이는 스택 마지막 건물 높
width = i if not stack else i - stack[-1] - 1 # i번째 까지의 최소 높이
area = height * width # 면적
max_area = max(max_area, area) # 최대 면적 구해준다.
stack.append(i) # 스택이 비어있으면
while stack: # 스택이 남아있으며 예제2번같이 똑같이 해준다.
height = heights[stack.pop()]
width = n if not stack else n - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
print(max_area)
플래문제가 궁금해서 많이 제출하고 정답률 높은 문제를 한 번 풀어보았다.
이 문제는 스택을 사용해주어야한다.
최댓값을 가져오려면 다음 들어올 건물이 스택에 있는 건물보다 높아야하고 그렇지 않은경우에 넓이를 최신화 시켜주면된다.
만약 예제처럼
높이가 2, 1, 4, 5, 1, 3, 3 이렇게 오면
스택에 2가 들어가있고 1이 들어오면 높이가 낮아지므로 최댓값을 최신화 시켜준다.
그러면 높이는 stk에서 뽑은 값 이다.
stack이 비어있지 않을 경우, 즉 이전에 처리한 직사각형이 있을 경우에는 현재 직사각형의 인덱스 i와 스택의 상단에 있는 직사각형의 인덱스 stack[-1] 사이의 거리를 구한다.
- stack[-1]은 스택의 가장 위에 있는 직사각형의 인덱스를 의미한다.
- i - stack[-1] - 1을 계산하면, 현재 직사각형과 스택의 상단 직사각형 사이에 있는 직사각형의 개수가 된다. .
i = 4일때 예를들어 보면
스택에섯 [1,4,5] 가 들어오고 1과 만나면 서 5와 4 를 팝한다.
그럼
5를 pop할때 (4-2-1) * 5
4를 pop할때 (4-1-1) * 4
앞에께 witdh 가 되고 뒤에가 높이가 된다.
다 하고나면 스택에는 [1,4,5,6] 이 남게 된다.
그럼 남은 부분에서도 넓이를 처리해 주어야한다.
근데 여기서는 width 대신
width = n if not stack else n - stack[-1] - 1n으로 바꿔줘야한다.
간단하게 말하면 6일때는 h 3이고 w = 1이다
5일때는 h 3 w 2
4일때는 h 1 w 3
1 일때는 h 1 w 7
이렇게 되는것이다.
그거를 식으로 나타태면
height = heights[stack.pop()]
width = n if not stack else n - stack[-1] - 1
area = height * width이렇게 된다.
댓글