오늘의 코테 문제!

오늘은 일정때문에 발표시간까지 문제를 못풀었당

class Solution {

    public int maximalRectangle(char[][] matrix) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)

            return 0;

        int rows = matrix.length;

        int cols = matrix[0].length;

        int[] heights = new int[cols + 1];

        int maxArea = 0;

        for (char[] row : matrix) {

            for (int i = 0; i < cols; i++) {

                heights[i] = (row[i] == '1') ? heights[i] + 1 : 0;

            }

            int n = heights.length;

            for (int i = 0; i < n; i++) {

                for (int j = i, minHeight = Integer.MAX_VALUE; j < n; j++) {

                    minHeight = Math.min(minHeight, heights[j]);

                    int area = minHeight * (j - i + 1);

                    maxArea = Math.max(maxArea, area);

                }

            }

        }

        return maxArea;

    }

}

클럽장님의 풀이 방법 그리고 다른 사람의 풀이를 참고했다. 아직 DP를 통해서 규칙을 찾는 것도 어렵고 규칙을 어떻게 활용하는지도 잘 모르겠다 ㅠㅠ

참고로 오늘 DP문제를 백준 실버단부터 풀어봤는데 아직 익숙하지 않고 어려운 부분이 많은 것 같다.

기초 DP문제 세 가지 모음

1로만들기
1,2,3더하기
계단오르기

모두 다 나에게 어려웠음 ㅋ

REVIEW

DP는 아직도 헷갈리고 어려운 부분이 많다. 사실 DP뿐만 아니라 그래프, 재귀, BFS & DFS를 이용한 탐색 자주 출제되는 부분이 많이 약한편이다. 더 많이 풀어보고 더 많이 연습해보자!

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL