[Baekjoon]백준 1725 히스토그램(플래티넘 5) - Python

문제설명 1

문제설명 2

이 문제는 이전에 풀었던 6549 히스토그램에서 가장 큰 직사각형와 굉장히 유사하다

그래서 조금 고민해보다가 이전의 코드를 활용하며 다시 복습하는 느낌으로 코드를 작성하였다

그러나, 해당 코드의 함수를 그대로 제출하였더니 틀렸습니다가 결과로 나왔다

# 백준 6549 히스토그램에서 가장 큰 직사각형
import sys

def sol(Rec):
    Rec.append(0)  # 마지막 원소로 작은 값 0을 추가하여 스택이 비워지도록 도와줌
    stack = []
    max_area = 0

    for i in range(len(Rec)):
        while stack and Rec[stack[-1]] > Rec[i]: # 스택의 최상단 높이보다 작은 경우 max_area 갱신
            height = Rec[stack.pop()]
            if not stack:
                width = i  # 스택이 비어 있다면, 현재 막대는 0부터 i까지 확장 가능
            else:
                width = i - stack[-1] - 1  # 왼쪽의 낮은 막대 바로 오른쪽부터 현재 i-1까지 확장 가능
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

while True:
    Rec_ = list(map(int, sys.stdin.readline().split()))
    if Rec_[0] == 0:
        break
    Rec = Rec_[1:]
    print(sol(Rec))

그래서 뭐가 문젠지 고민해보다가...다른 반례를 보고 무언가 이상한 점을 알 수 있었다

10
1
2
3
4
5
10
7
8
9
10
solve : 35

해당 예제를 입력하면 35가 나와야하는데, 처음에 제출한 코드는 10이 나온다

엥...? 너무 다른데 싶어서 계속 고민해보다가 for문에서 size조건에 의해 마지막 부분은 처리가 되지 않는듯해서

for문의 size부분을 range(size)가 아니라 range(size+1)로 수정하였더니 정답임을 확인할 수 있었다

생각보다 너무 간단한 부분에서 코드가 잘못 된거라 조금 허무하긴 했지만, 스택을 다시 한 번 복습하는 

좋은 기회가 된 것이라 생각한다 아무 참고 코드도 없이 혼자 풀기위해 노력해야겠다...

(추가) 이 코드의 동작 과정을 문제에서 주어진 예제로 설명하겠다

i	Rec[i]	스택 상태	처리 과정	max_area
0	2	[0]	스택이 비어있기때문에 push	0
1	1	[1]	Rec[0] > Rec[1], pop → 넓이 계산: 2 × 1 = 2	2
2	4	[1, 2]	스택이 비어있기때문에 push	2
3	5	[1, 2, 3]	스택이 비어있기때문에 push	2
4	1	[1, 4]	Rec[3] > Rec[4], pop → 넓이 계산: 5 × 1 = 5 Rec[2] > Rec[4], pop → 넓이 계산: 4 × 2 = 8	8
5	3	[1, 4, 5]	스택이 비어있기때문에 push	8
6	3	[1, 4, 5, 6]	스택이 비어있기때문에 push	8
7	0	[7]	Rec[6] > Rec[7], pop → 넓이 계산: 3 × 1 = 3 Rec[5] > Rec[7], pop → 넓이 계산: 3 × 2 = 6 Rec[4] > Rec[7], pop → 넓이 계산: 1 × 5 = 5 Rec[1] > Rec[7], pop → 넓이 계산: 1 × 7 = 7	8

해당 표를 보고 그림을 그리다보면 조금이나마 도움이 될 것이라 생각한다

이는 높이에 따라 index를 이동하면서 max_area를 갱신하는 과정이다

import sys
input = sys.stdin.readline

size = int(input())
Rec = [int(input()) for _ in range(size)]

Rec.append(0)  # 남아있는 모든 막대를 처리하기 위함
stack = []     # index 저장
max_area = 0   # 최대 넓이
for i in range(size+1):
    while stack and Rec[stack[-1]] > Rec[i]:  # 높이가 더 높은 경우
        height = Rec[stack.pop()]
        if not stack:   # 스택이 비어있는 경우
            width = i   # 현재 위치가 너비
        else:
            width = i - stack[-1] - 1  # 현재 index와 스택 최상단 index 사이의 거리 계산
        max_area = max(max_area, height * width) # 최대 넓이 갱신
    stack.append(i)  # index 저장

print(max_area)