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