[LeetCode] 85. Maximal Rectangle (Daily Question)

문제

---

 

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

 

0과 1로 이루어진 테이블이 주어졌을 때, 1로 만들 수 있는 가장 큰 사각형의 넓이를 구하는 문제이다.

 

Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:
Input: matrix = [["0"]]
Output: 0

Example 3:
Input: matrix = [["1"]]
Output: 1

 

풀이

---

아이디어

matrix[0][0]부터 살펴보며 1이 나올 경우 오른쪽과 아랫쪽으로 뻗어나가며 사각형의 넓이를 구한다.

* 좌상단에서부터 살펴보기 때문에 왼쪽과 위쪽으로 뻗어나갈 필요는 없다.

 

사각형의 넓이를 구할 때는 해당 좌표(x, y)부터 행을 증가시키며 각 행의 최대열을 찾아 행(x~x+a) 넓이를 구해 최대값을 반환한다.

여기서 x행의 최대열은 x-a행(a>0)의 최대열을 넘지 못한다.

* 사각형을 만들기 위해서는 반듯해야하기 때문이다.

 

코드

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        def get_area(x, y):

            # 열의 최대값
            # 2행의 최대열이 10이라도 1열의 최대열이 3이라면 2열의 최대열을 3으로 줄여야 함 (사각형을 만들어야 하므로)
            wall = len(matrix[0])

            area = 1
            xx = x
            # 행을 증가시키며 최대로 뻗어나갈 수 있는 열을 찾음
            while xx < len(matrix) and matrix[xx][y] == "1":
                yy = y
                while yy < wall and matrix[xx][yy] == "1":
                    yy += 1
                
                wall = yy
                area = max([area, (wall-y) * (xx-x+1)])
                xx += 1
                
            return area
        
        area = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                # 현재 위치에서 만들 수 있는 가장 큰 사각형의 넓이가 현재 저장된 넓이(area)를 넘지못하면 차례를 넘김 
                if (len(matrix)-i) * (len(matrix[0])-j) <= area: break
                if matrix[i][j] == '1':
                    area = max([area, get_area(i, j)])

        return area

---

 

후기

---

난이도

아이디어를 떠올리는데 시간이 많이 걸렸다.거기다가 생각해낸 방식은 시간 초과가 나서 최적화과정이 필요했다.그래도 구현은 어렵지 않아서 다행이었다.

 

처음에 DFS느낌으로 풀다가 시간초과가 나서 다시 풀었다.

언제쯤에야 시간견적을 잘 낼 수 있을까...