알고리즘/99Club

99클럽 코테 스터디 22일차 TIL + Java Algorithm

dami97 2024. 8. 12. 23:53
반응형

소개

  • 알고리즘 스터디를 참여하며 작성하는 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. 히스토그램 높이 계산
    • 각 행을 기준으로 해당 행까지의 연속된 1의 개수를 세어 히스토그램 높이를 계산합니다.
  2. 최대 직사각형 계산
    • 각 행의 히스토그램에서 가능한 모든 직사각형의 넓이를 계산하고, 그중 가장 큰 값을 선택합니다.
  3. 결과 반환
    • 각 행에서 구한 최대 넓이 중 가장 큰 값을 반환합니다.

 

풀이

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'이면 이전 높이에 1을 더하고, '0'이면 높이를 0으로 초기화합니다.
  2. 최대 직사각형 계산
    • 각 열을 시작점으로 하여 가능한 모든 직사각형의 넓이를 계산합니다.
    • h는 현재 계산 중인 직사각형의 최소 높이로, w는 너비를 나타냅니다. 이 값을 이용해 가능한 모든 직사각형의 넓이를 구하고, 최대 넓이를 갱신합니다.
  3. 결과 반환
    • 모든 행에서 계산된 직사각형의 넓이 중 가장 큰 값을 반환하여 최대 직사각형의 넓이를 구합니다.

 

 

마무리하며

  • 이번 문제를 통해 2D 배열을 활용한 동적 계획법과 히스토그램을 결합하여 문제를 해결하는 방법을 학습했습니다.
  • 각 행을 히스토그램으로 보고 문제를 접근하는 방법으로 문제를 해결했습니다.