99클럽 코테 스터디 22일차 TIL, leetcode / maximal-rectangle

🔑 오늘의 학습 키워드 : 스택

🔗 문제링크 https://leetcode.com/problems/maximal-rectangle/

 

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        rows = len(matrix)
        cols = len(matrix[0])
        max_area = 0
        heights = [0] * cols
        
        for i in range(rows):
            for j in range(cols):
                # 높이 갱신
                if matrix[i][j] == '1':
                    heights[j] += 1
                else:
                    heights[j] = 0
            
            # 현재 행의 heights 배열에 대해 최대 직사각형 넓이 계산
            max_area = max(max_area, self.largestRectangleArea(heights))
        
        return max_area
    
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 히스토그램에서 최대 직사각형 넓이 구하는 방법
        stack = []
        max_area = 0
        heights.append(0)  # 마지막까지 남은 높이를 처리하기 위해

        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, h * w)
            stack.append(i)
        
        heights.pop()  # 복구
        return max_area

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

이전에 비슷한 유형의 문제를 풀었다고 생각을 했는데 그 문제는 정사각형을 가지고 누적합을 구하는 것이었다.

 

그래서 이번 문제는 다르다고 판단이 들었고 직사각형이 결정되는 조건에 대해 생각해봤다.

 

일자 가로, 일자 세로, 그리고 네모 모양의 직사각형이 존재하며 이들을 가지고 계산을 하는 방법을 찾아야 했다.

 

⏰ 예상 시간 복잡도 O(N)

제한 사항

Constraints:

• rows == matrix.length
• cols == matrix[i].length
• 1 <= row, cols <= 200
• matrix[i][j] is '0' or '1'.

😎 알고리즘 개요

1. 1로 되어 있는 영역 찾기

for i in range(rows):
    for j in range(cols):
        # 높이 갱신
        if matrix[i][j] == '1':
            heights[j] += 1
        else:
            heights[j] = 0

    # 현재 행의 heights 배열에 대해 최대 직사각형 넓이 계산
    max_area = max(max_area, self.largestRectangleArea(heights))

우선 세로로 되어 있는 영역을 생각해보면 아래로 쭉 가다가 1을 만나면 성장, 0을 만나면 끝 인 것을 알 수 있다.

 

그렇게 세로로 이어져 있는 높이를 찾았다.

 

그 후 구한 높이를 가지고 해당 row에서 넓이의 최대를 구하면 된다

2. 가장 큰 영역 계산 하기

def largestRectangleArea(self, heights: List[int]) -> int:
    # 히스토그램에서 최대 직사각형 넓이 구하는 방법
    stack = []
    max_area = 0
    heights.append(0)  # 마지막까지 남은 높이를 처리하기 위해

    for i in range(len(heights)):
        while stack and heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)

    heights.pop()  # 복구
    return max_area

 

이 함수는 자기보다 작은 높이를 만났을때 실행되는 stack 함수이다.

 

직사각형이 결정될 때는 만약

 

3  2  2  0  1 이렇게 있다고 가정하면

 

2 (높이) * 3 (길이) 이런 식으로 결정을 했기 때문에 위와 같이 스택에 담아서 구해줬다.

 

✅ 오늘의 회고

- 스택 풀이는 잘 알아두면 좋은 것 같다.

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL