[프로그래머스] Lv2. 가장 큰 정사각형 찾기 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 가장 큰 정사각형 찾기

문제

제한사항

📌 내가 생각한 풀이

DP를 이용하여 풀자! 현재값을 기준으로 왼쪽, 위, 왼쪽대각선위를 보고 가장 작은 값에 + 1 해준 값이 가장 큰 정사각형이다.

function solution(board)
{
    let answer = 0 ;
    let width = 0;
    if (board.length <= 1 || board[0].length <= 1) return 1;
    for(var i =1; i<board.length; i++){
        for(var k = 1; k<board[0].length; k++){
            if(board[i][k] > 0){
                let left = board[i][k-1];
                let up = board[i-1][k];
                let cross = board[i-1][k-1];
                let min = Math.min(left, up, cross);
                board[i][k] = min+1;
                width = Math.max(width, min+1);
            }
        }
    }
    return width**2;
}

📌 느낀점

DP로 어떻게 해결할까 고민하다가 인터넷을 참고하여 풀었다. 배열의 누적합을 이용한 완전탐색 회피, DP 등등 2차원 배열의 문제가 자주 출제 되지만 조금 약한 것 같아 추가로 공부해야겠다. 참고로 이번 문제는 테스트케이스상의 약간의 오류가 존재하는 것 같다.