[프로그래머스] 가장 큰 정사각형 - 자바스크립트

https://programmers.co.kr/learn/courses/30/lessons/12905#

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

문제 플로우는 간단하지만 Boundary Condition이 조금더 귀찮은 문제이다.

문제의 플로우는 다음과 같다.

1. board의 1, 1에서 시작하여 n, n까지 for문 두개를 순회한다.i, j

2. board[i][j]의 [i-1, j-1], [i, j-1], [i-1,j-1], [i,j]모두 0이 아닌경우, [i,j]를 제외한 숫자에서 가장 작은 숫자에 +1을 더한다

3. 이 과정중 가장 큰숫자를 제곱한다.

이 순서대로 가지만 이 문제에는 여러 Boundary Condition이 존재한다

1. i가 최대0인경우, j가 최대 0인경우 이경우에는, 각 경우에서 가장 큰 숫자가 return 되야한다. 이유는, 0아니면 1만 나올 수 있기 때문이다.

2. for문에서 제외해준, 0,0 1,0 0,1을 제외하고 모두 0이나온 경우이다. 이 경우에, zeroCheck라는 변수를 만들어서, 이 숫자보다 작은 값으로 return이 될꺼 같으면 그 값을 올려주게 Boundary Condition을 넣으면 된다.

 

function solution(board){
    const h = board.length
    const w = board[0].length
    //boundary condition
    if(h===1){return Math.max(...board[0])}
    if(w===1){
        let wmax
        for(let i=0;i<w;i++){
            if(wmax<board[i]){
                wmax = board[i]
            }
        } return wmax}
    // calc
    let max =0
    let zeroCheck = Math.max(board[0][0], board[1][0], board[0][1])
    for(let j=1;j<w;j++){
        for(let i=1;i<h;i++){
            if(board[i-1][j-1]!==0&&board[i-1][j]!==0&&board[i][j-1]!==0&&board[i][j]!==0){
                board[i][j]=Math.min(board[i-1][j-1], board[i-1][j], board[i][j-1])+1
                if(max<board[i][j]){
                    max = board[i][j]
                }
            }
        }
    }
    max = Math.max(max, zeroCheck)
    return max*max
}