[Javascript] 가장 큰 정사각형 (12905)

문제링크

코딩테스트 연습 - 가장 큰 정사각형 찾기

 

접근 방법

문제를 살펴보면 패턴이 보인다.
1 1        1 1
1 1  =>  1 2

1 1 1        1 1 1
1 1 1        1 2 2
1 1 1  =>  1 2 3

이처럼 각 축을 x, y라 했을때 (x, y), (x+1, y), (x, y+1), (x+1, y+1)이 모두 1이면
(x+1, y+1)은 (x, y), (x+1, y), (x, y+1)의 값 + 1 이된다.

이를 통해 dp를 이용하여 문제를 풀었다.

주의점

dp를 board와 같은 크기로 설정하면 for문에서 범위 설정에 문제가 생긴다.
board의 행과 열을 +1씩 키운 뒤, dp(1,1) === board(0,0)이라는 생각을 갖고 풀이해야 범위에서 에러가 발생하지 않는다.

 

 

 

function solution(board)
{
    var answer = 1234;
    dp = Array.from({length : board.length+1}, () => new Array(board[0].length+1).fill(0))
    let maxLen = 0;
    
    for(let x = 1; x < board.length+1; x++){
      for(let y = 1; y < board[0].length+1; y++){
        if(board[x-1][y-1] === 1){
          dp[x][y] = Math.min(dp[x-1][y-1], dp[x-1][y], dp[x][y-1]) + 1;
        }
        maxLen = maxLen > dp[x][y] ? maxLen : dp[x][y]
      }
    }
    
    answer = Math.pow(maxLen, 2);
    
    return answer;
}