프로그래머스 가장 큰 정사각형 찾기 (level 2)

나의 1차 풀이 (풀이 시간 : 32분)

function solution(board)
{
    var answer = 0;

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] === 1) {
                let check = true;
                for (let count = 1; count <= board.length; count++) {
                    if (!check) break;
                    if (i+count < board.length && j+count < board[0].length) {
                        for (let k = j; k <= j+count; k++) {
                            if (board[i+count][k] === 0) {
                                check = false;
                                break;
                            }
                        }
                        if (check) {
                            for (let k = i; k <= i+count; k++) {
                                if (board[k][j+count] === 0) {
                                    check = false;
                                    break;
                                }
                            }
                        }
                        
                    } else {
                        break;
                    }
                    if (check) answer = Math.max(answer, (count+1)**2);
                }

            }
        }
    }
    return answer;
}

board를 탐색하면서 1을 발견하면 count를 1부터 늘리면서 정사각형을 이루며 퍼지면서 원소에 0이 있는지 없는지 검사한다. 0이 있으면 check 변수를 false로 바꾼다.

나의 2차 풀이

function solution(board)
{
    let answer = 0;
    if (board.length < 2 || board[0].length < 2) {
        if (board[0].includes(1)) return 1;
    }
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] === 1 && (Math.min(board.length-i, board[0].length-j) > Math.sqrt(answer))) {
                answer = Math.max(1,answer);
                let check = true;
                for (let count = 1; count <= board.length; count++) {
                    if (!check) break;
                    if (i+count < board.length && j+count < board[0].length) {
                        for (let k = j; k <= j+count; k++) {
                            if (board[i+count][k] === 0) {
                                check = false;
                                break;
                            }
                        }
                        if (check) {
                            for (let k = i; k <= i+count; k++) {
                                if (board[k][j+count] === 0) {
                                    check = false;
                                    break;
                                }
                            }
                        }
                        
                    } else {
                        break;
                    }
                    if (check) answer = Math.max(answer, (count+1)**2);
                }

            }
        }
    }
    return answer;
}

생각나는 예외들을 모두 처리해주느 정확성 평가에서는 만점이 나왔다. 하지만 효율성 측면에서 통과하지 못했다.

아예 다른 방법으로 접근해보자..