[leetcode] 85. Maximal Rectangle

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

---

0과 1로 이루어진 배열이 주어질 때, 1로만 이루어진 직사각형의 최대 크기를 구하라.

---

배열 크기가 row x cols 인데 row, cols 모두 최대 200이다. row, cols 의 최대크기가 동일하니까 해당 크기를 N이라 봤을 때, 직사각형의 크기를 구하려면 직사각형의 왼쪽 위 지점을 구하기 위해 O(N^2), 이때, 오른쪽 아래 지점을 구하기 위한 O(N^2)가 드므로 완탐으로 구하면 총 O(N^4)이 소요된다.

N의 최대 크기는 200이므로 TLE가 발생할 것이다. 시간을 좀 더 줄 일 수 있는 방법을 찾아야한다.

 

배열을 탐색하면서 오른쪽 아래 지점을 고정시키고 왼쪽 위 지점을 탐색해가면서 만들 수 있는 직사각형의 크기를 구할것이다.

이 때, 탐색하면서 만들 수 있는 사각형의 최대 높이를 저장해놓는다면 탐색 수를 줄일 수 있다.

[그림 1]

 

[그림 1] 배열을 예로 들어보자.

배열 중 2행을 기준으로 볼 것이며 오른쪽 아래는 2행 4열 (빗금친 부분)으로 고정했을 때, 구할 수 있는 최대 직사각형의 크기를 구해보자.

[그림 1]의 오른쪽 그림은 2행을 바닥으로 했을 때 최대 높이이다.

 

[그림 2]

먼저 기준이 되는 (2, 4) 를 포함, 4열로 만들 수 있는 최대 직사각형 크기는 3이다.

두 번째로 3~4열로 만들 수 있는 최대 직사각형의 높이는 3~4열의 높이들 중 최소값인 2, 너비는 2(3~4)이므로 최대 직사각형 크기는 4이다.

 

[그림 3]

2~4 열로 만들 수 있는 최대 직사각형 높이는 2~4열의 높이들 중 최소값인 2, 너비는 3(2~4)이므로 최대 직사각형 크기는 2x3 = 6이다.

1~4 열로 만들 수 있는 최대 직사각형 높이는 1, 너비는 4이므로 최대 직사각형 크기는 4이다.

[그림 4]

0~4 열로 만들 수 있는 직사각형 높이는 0이므로 앞으로 만들 모든 직사각형들의 높이도 0일 것이다. 따라서 탐색을 종료한다.

 

이처럼 배열을 탐색해가면서 height[j] = j열의 높이. 를 구해둔다면 직사각형의 오른쪽 아래 지점을 고정해두었을 때, 직사각형의 왼쪽 위 지점을 구하기 위해 O(N^2) 만큼 탐색하는게 아니라 배열의 열 크기만큼만 탐색하면 최대 직사각형 크기를 구할 수 있으므로 O(N) 으로 왼쪽 위 지점을 구할 수 있다.

 

이 방법으로 구하는 경우 오른쪽 아래 지점을 구하는데 드는 시간 N^2 에 오른쪽 아래 지점 고정 시 최대 직사각형을 구하는데 드는 시간 O(N)이 소요되므로 총 시간복잡도는 O(N^3)이 된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/85.%20Maximal%20Rectangle.cpp