84. Largest Rectangle in Histogram

두둥

 

제 LeetCode 인생 첫 Hard 문제입니다.

 

긴장..

https://leetcode.com/problems/largest-rectangle-in-histogram/

Largest Rectangle in Histogram - LeetCode

 

바로 Largest Rectangle in Histogram입니다. 이 문제의 경우엔 백준에도 있는 문제입니다.

 

https://www.acmicpc.net/problem/6549

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

되게 유명한 문제에요. 참고로 L 기업의 코딩테스트로도 나왔대요.

 

그럼 풀어봅시다.

---

설명을 하자면, 그려진 히스토그램 내에서 가장 큰 직사각형을 찾는 겁니다. 아마 사진 보면 딱 바로 알거에요.

그렇다면 이걸 도대체 어떻게 찾느냐가 문제인데, 이 문제를 해결하기위해 저희는 스택을 사용해볼겁니다.

 

우선 거두절미하고 스택에 [1, 5, 6]이 있다고 가정을 해봅시다. 거기서 높이 2를 가진 히스토그램이 들어온다고 했을 때, 그 2는 앞 전에 나온 5, 6의 넓이 변화에 영향을 미칠까요?

 

안 미치겠죠? 여기서 이해가 잘 안되면 높이 2가 아닌 7을 가진 히스토그램이 들어왔다고 생각해봅시다. 그 7은 이 전의 값과 상호작용하여 더 큰 값을 만들어 낼 수 있습니다.

 

물론 이 경우를 생각해볼 수 있습니다. [1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 1, 1, 1, 1, 1, 1, 1 ,1, 1, 1] 이 경우엔 길다란 1의 높이를 가진 직사각형이 최대 넓이가 되겠죠.

 

그렇기 때문에 저희는 높이만을 스택에 저장하는게 아닌 인덱스 위치 저장을 같이 해나갈겁니다.

 

그렇다면 스택엔 [[1, 1], [5, 2], [6, 3]]이 있을 것이고 새로 들어올 값은 [2, 4]가 되겠죠. 그리고 앞 전에 얘기했던 방법으로 2보다 큰 값들은 전부 stack에서 꺼내보도록 하겠습니다. 꺼낼 땐 새로 들어오는 [2, 4]의 위치 기준으로 그 꺼내는 값의 넓이를 읽어서 최댓값을 갱신해가면서 꺼내야합니다.

 

[6, 3]이 꺼내질 것이고 높이 6 * (4(새로 들어올 높이 2의 인덱스) - 3(stack에서 pop 당한 높이 6의 인덱스))를 해주면 넓이가 구해지겠죠.

 

그리고 다음 값을 꺼내봅시다. [5, 2]가 나올 것이고 5 * (4 - 2)가 되어 넓이 10이 구해질 겁니다. 그리고 남은 스택의 데이터엔 높이 1짜리 히스토그램이 있으니 루프는 멈출 것이고, 저희가 넣을 [2, 4]가 들어가겠죠.

 

라고 생각하시면 경기도 오산입니다.

오산이라구요.

앞전에 스택에서 제거했던 애들은 곧 넣을 [2, 4]의 높이 2보다 큰 값으로서 2의 기준에선 넓이 확장에 도움이 되는 애들입니다. 그렇기에 인덱스를 수정하고 넣어줘야합니다.

 

그 인덱스 수정은 마지막에 pop을 했던 [5, 2]의 인덱스를 계승해주면됩니다.

 

즉, [2, 2]의 값이 stack에 추가되는 것이죠.

 

여기까지가 핵심 로직입니다.

 

그렇다고 여기가 끝일까요? N개의 히스토그램 높이를 다 봤다고 했을 시, stack에 데이터가 남아있을 확률이 다분합니다. 그렇기에 이 값들도 전부 전수검사를 해야하는데, 이 때의 indexing 기준은 무엇으로 잡을까요?

 

즉, 앞에서 마지막으로 pop한 높이 * (현재 인덱스 - 마지막으로 pop 한 index)를 했을 때 현재 인덱스가 무엇이 되어야 하느냐 입니다. 앞 전에는 새로 들어올 값의 인덱스가 현재 인덱스가 되었죠.

 

간단합니다. N으로 하면됩니다. 결국 데이터는 0 ~ N - 1까지 순회를 하게 될 것이고 N 번째는 히스토그램의 제일 마지막 변을 바라보고 있겠죠. 그렇기에 그 변에서 stack에 남아있는 데이터를 기준으로 직사각형을 구하면 가로로 길다라게 직사각형 넓이를 구할 수 있는 방법이 됩니다.

 

이해가 안되시면 바로 코드 들어갑니다잉

 

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        result = 0
        for idx, height in enumerate(heights):
            if stack == []: # stack에 없으면
                stack.append([idx, height]) # 무조건 때려넣어
            else:
                width = idx # 현재 값의 idx 저장
                while stack != [] and stack[-1][1] > height: # top 값이 height보다 클 시
                    value = stack.pop()
                    width = value[0] # 마지막 pop한 히스토그램 idx 갱신
                    size = value[1] * (idx - value[0]) # 넓이 구하기
                    if result < size: # 최댓값 갱신
                        result = size
                stack.append([width, height])
        for value in stack: # 스택에 남은 애들 전부 계산
            size = value[1] * (len(heights) - value[0]) # 기준은 길이 N으로
            if result < size:
                result = size
        return result

되게 짧죠?

 

처음부터 코드를 보여줄 걸 그랬어..

 

첫 Hard 문제였습니다.

 

굉장히 어렵네요 ;;

 

앞으로 더 공부 빡세게 해봅시다 !

---

이상 84. Largest Rectangle in Histogram였습니다. ^_^