[JS] 연습문제 - 가장 큰 정사각형 찾기

function solution(board) {
  let row = board.length;
  let column = board[0].length;

  if (row <= 1 || column <= 1) return 1;

  let answerLength = 0;
  for (let i = 1; i < row; i++) {
    for (let j = 1; j < column; j++) {
      if (board[i][j] >= 1) {
        let cross = board[i - 1][j - 1];
        let up = board[i - 1][j];
        let left = board[i][j - 1];
        if (cross >= 1 && up >= 1 && left >= 1) {
          board[i][j] = Math.min(cross, up, left) + 1;
        }
        answerLength = Math.max(answerLength, board[i][j]);
      }
    }
  }
  return answerLength ** 2;
}

 

프로그래머스

프로그래머스

 

1. 주어진 배열에서 0번째가 아닌 i = 1, j = 1부터 기준을 잡습니다.
2. 그 기준점이 1 이상일 때, 왼쪽위 대각선, 위, 왼쪽 세 부분의 값이 모두 1 이상인 경우 그 기준점에 세 군데의 값중 작은 값에 + 1을 한 값을 할당합니다.
3. 최종적으로 그 끝의 값에 정사각형의 변의 길이가 할당됩니다. 그 값의 제곱을 리턴합니다.

 

개인적으로 문제 자체의 의도를 알겠으나 테스트케이스 부분에서 아쉬운 점들이 많은 문제였습니다.
위 코드로는 다 통과가 되지만 혹시 놓친 부분은 없을까 생각해봤는데
예를 들어, 첫째 행 혹은 첫째 열에 1이 하나라도 있고 그 외에는 전부 0인 경우 분명히 1을 리턴해야하는데(아무튼 1이 하나 있으니 가장 큰 정사각형의 넓이는 1이기 때문에) 위 코드는 0을 리턴하게 됩니다.
이 부분을 해결하고 싶어 board.flat().find((x) => x === 1)이 true와 false를 나눠서 처리하려 하였는데 시간 복잡도로 효율성에서 초과가 나옵니다.