반응형
소개
- 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
- TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
- 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.
문제 & 키워드
- LeetCode - Maximal Rectangle (문제 링크)
- 동적 계획법 (Dynamic Programming)
- 히스토그램
- 2D 배열
문제 설명
주어진 이진 행렬에서 1로만 이루어진 가장 큰 직사각형의 넓이를 구하는 문제입니다. 0과 1로 이루어진 행렬에서 1로 구성된 가장 큰 직사각형의 면적을 구하는 문제입니다.
제약사항
- rows == matrix.length
- cols == matrix[i].length
- 1 ≤ row, cols ≤ 200
- matrix[i][j]는 '0' 또는 '1'입니다.
입출력 예
예제 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.
예제 2:
Input: matrix = [["0"]]
Output: 0
예제 3:
Input: matrix = [["1"]]
Output: 1
문제 접근
이 문제는 2차원 배열에서 1로 구성된 최대 직사각형을 찾아야 합니다.
이를 해결하기 위해서는 각 행을 히스토그램으로 보고 문제를 해결할 수 있습니다.
행마다 히스토그램의 높이를 갱신하며, 각 행에서의 최대 직사각형 넓이를 계산하고, 이를 기반으로 전체에서의 최대 넓이를 구합니다.
- 히스토그램 높이 계산
- 각 행을 기준으로 해당 행까지의 연속된 1의 개수를 세어 히스토그램 높이를 계산합니다.
- 최대 직사각형 계산
- 각 행의 히스토그램에서 가능한 모든 직사각형의 넓이를 계산하고, 그중 가장 큰 값을 선택합니다.
- 결과 반환
- 각 행에서 구한 최대 넓이 중 가장 큰 값을 반환합니다.
풀이
class Solution {
public int maximalRectangle(char[][] matrix) {
int answer = 0;
int row = matrix.length;
int col = matrix[0].length;
int[] heights = new int[col];
for (int y = 0; y < row; y++) {
for (int c = 0; c < col; c++) {
// 현재 행에서 히스토그램 높이 계산
heights[c] = matrix[y][c] == '1' ? heights[c] + 1 : 0;
}
// 각 열에서의 최대 직사각형 넓이 계산
for (int x = 0; x < col; x++) {
int h = Integer.MAX_VALUE;
int w = 0;
for(int t = x; t < col; t++){
h = Math.min(h, heights[t]); // 가장 작은 높이를 유지
w = t - x + 1; // 현재 열의 너비
answer = Math.max(answer, w * h); // 최대 넓이 갱신
}
}
}
return answer;
}
}풀이 설명
- 히스토그램 높이 계산
- 각 행에 대해 히스토그램 높이를 계산합니다. 연속된 1의 개수를 계산하여 히스토그램의 높이로 삼습니다. 만약 현재 위치가 '1'이면 이전 높이에 1을 더하고, '0'이면 높이를 0으로 초기화합니다.
- 최대 직사각형 계산
- 각 열을 시작점으로 하여 가능한 모든 직사각형의 넓이를 계산합니다.
- h는 현재 계산 중인 직사각형의 최소 높이로, w는 너비를 나타냅니다. 이 값을 이용해 가능한 모든 직사각형의 넓이를 구하고, 최대 넓이를 갱신합니다.
- 결과 반환
- 모든 행에서 계산된 직사각형의 넓이 중 가장 큰 값을 반환하여 최대 직사각형의 넓이를 구합니다.
마무리하며
- 이번 문제를 통해 2D 배열을 활용한 동적 계획법과 히스토그램을 결합하여 문제를 해결하는 방법을 학습했습니다.
- 각 행을 히스토그램으로 보고 문제를 접근하는 방법으로 문제를 해결했습니다.
