파이썬으로 히스토그램에서 가장 큰 직사각형 넓이 찾기

히스토그램의 각 막대 높이를 나타내는 숫자 리스트가 주어졌다고 가정해 봅시다. 이 문제의 목표는 막대들 아래에 만들 수 있는 가장 큰 직사각형의 넓이를 구하는 것입니다.

예를 들어 입력이 nums = [3, 2, 5, 7]이라면,

출력은 다음 그림처럼 10이 됩니다.

해결 접근 방법

이 문제는 스택(stack) 자료구조를 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 막대를 기준으로 "이 막대를 높이로 하는 직사각형이 좌우로 얼마나 확장될 수 있는지"를 계산하는 것입니다.

단계별로 살펴보면 다음과 같습니다.

1. 스택 stk를 생성하고 초기값으로 -1을 삽입합니다.
2. heights 리스트의 끝에 0을 추가합니다. 이렇게 하면 반복문이 끝나기 전에 스택에 남아 있는 모든 막대가 강제로 처리됩니다.
3. ans를 0으로 초기화합니다.
4. i를 0부터 heights의 길이까지 반복하면서 다음을 수행합니다.
   • heights[i]가 스택 최상단(top)의 높이보다 작은 동안:
     • h := 스택 최상단의 높이 값을 꺼냄(pop)
     • w := i - 스택 최상단 인덱스 - 1
     • ans := ans와 h × w 중 더 큰 값으로 갱신
   • i를 스택에 push합니다.
5. 최종적으로 ans를 반환합니다.

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

class Solution:
   def solve(self, heights):
      stk = [-1]
      heights.append(0)
      ans = 0
      for i in range(len(heights)):
         while heights[i] < heights[stk[-1]]:
            h = heights[stk.pop()]
            w = i - stk[-1] - 1
            ans = max(ans, h * w)
         stk.append(i)
      return ans

ob = Solution()
nums = [3, 2, 5, 7]
print(ob.solve(nums))

입력

[3, 2, 5, 7]

출력

10

동작 원리 설명

위 예제에서 [3, 2, 5, 7]의 경우, 높이 5와 7인 막대를 포함한 구간에서 폭 2, 높이 5인 직사각형(넓이 10)이 가장 큰 결과가 됩니다. 스택에는 항상 높이가 오름차순으로 유지되며, 더 낮은 막대를 만나는 순간 스택에 쌓여 있던 막대들이 하나씩 꺼내지면서 각각의 최대 직사각형 넓이가 계산됩니다. 이 방식은 모든 막대를 한 번씩만 push하고 pop하기 때문에 전체 시간 복잡도가 O(n)입니다.