[백준] 6549 - 히스토그램에서 가장 큰 직사각형 문제 풀이(파이썬,Python)

문제

6549번: 히스토그램에서 가장 큰 직사각형

들어가며

플레의 벽은 높았다..

 

코드

def largest_rectangle(histogram):
    stack = []  # 스택에는 인덱스를 저장합니다.
    max_area = 0  # 최대 넓이를 저장할 변수
    n = len(histogram)

    for i in range(n):
        # 현재 높이가 스택의 최상단 높이보다 작으면 넓이를 계산합니다.
        while stack and histogram[stack[-1]] > histogram[i]:
            height = histogram[stack.pop()]  # 스택에서 꺼낸 높이
            width = i if not stack else i - stack[-1] - 1  # 너비 계산
            max_area = max(max_area, height * width)  # 최대 넓이 갱신

        stack.append(i)  # 현재 인덱스를 스택에 추가

    # 히스토그램 끝까지 처리한 후, 스택에 남아 있는 값들 처리
    while stack:
        height = histogram[stack.pop()]  # 스택에서 꺼낸 높이
        width = n if not stack else n - stack[-1] - 1  # 너비 계산
        max_area = max(max_area, height * width)  # 최대 넓이 갱신

    return max_area

while True:
    l = list(map(int, input().split()))
    if l[0] == 0:
        break
    print(largest_rectangle(l[1:]))

풀이

이 문제는 스택으로 풀 수 있다.

단, 스택엔 히스토그램 수열의 인덱스를 넣는다.

 

히스토그램

Index:    0   1   2   3   4   5
Height:   2   1   5   6   2   3

 

초기 상태

stack = [] (스택은 비어 있음)

max_area = 0 (최대 넓이는 초기값으로 설정)

 

여기서 필요한 건 스택과 최대 넓이이다.

그리고 앞으로 인덱스를 하나씩 탐사하면서 스택에 push를 진행할 거다.

 

첫 번째 막대 (index = 0, height = 2)

스택이 비어 있으므로 현재 인덱스 0을 스택에 추가한다.

스택 상태는 0이 들어간다.

 

두 번째 막대 (index = 1, height = 1)

현재 높이 1이 스택의 최상단 높이(height = 2)보다 작으므로 다음과 같은 과정을 거친다.

• 스택에서 값을 꺼낸다. (stack.pop() -> 0)
• 꺼낸 높이 : height = 0이 가리키는 2가 된다.
• 너비 : width = index - stack.peek - 1 = 1 (여기선 스택이 비어 있기 때문에, 현재 인덱스를 넣는다)
• 넓이 : 높이 x 너비  = height x width = 2 x 1 = 2
• 최대 넓이 갱신 : max_area = max(max_area, area) = max(0,2) = 2

그리고 현재 인덱스 1을 스택에 추가한다.

 

세 번째 막대 (index = 2, height = 5)

스택에 2를 추가한다.

 

네 번째 막대 (index = 3, height = 6)

스택에 3을 추가한다.

 

다섯 번째 막대 (index = 4, height = 2)

여기서 중요한 건 높이인 2보다 작거나 같은 값이 나올 때까지, pop을 하고 최대 넓이 갱신을 하는 작업을 무한히 반복한다는 것이다.

• 스택에서 값을 꺼낸다. (stack.pop() -> 3)
• 꺼낸 높이 : height = 3이 가리키는 6이 된다.
• 너비 : width = index - stack.peek - 1 = 4 - 2 - 1 = 1  (3을 빼냈기 때문에, 2가 최대가 된다.)
• 넓이 : 높이 x 너비 = height x width = 6 x 1 = 6
• 최대 넓이 갱신 : max_area = max(max_area, area) = max(2,6) = 6

현재 스택엔 2인 인덱스가 peek에 존재한다.

2가 가리키는 값은 5, 즉 우리가 넣고자 하는 2보다 작다.

이전의 작업을 그대로 진행한다.

• 스택에서 값을 꺼낸다. (stack.pop() -> 2)
• 꺼낸 높이 : height = 2이 가리키는 5이 된다.
• 너비 : width = index - stack.peek - 1 = 4 - 1 - 1 = 2  (2을 빼냈기 때문에, 1이 최대가 된다.)
• 넓이 : 높이 x 너비 = height x width = 5 x 2 = 10
• 최대 넓이 갱신 : max_area = max(max_area, area) = max(6,10) = 10

이와 같은 작업을 처음 히스토그램 수열을 한 번 다 돌때까지 진행한다.

 

그 이후 만약, 스택에 값이 남아있다면 이전과 똑같이 진행하여 최대 넓이를 갱신한다.