가장 큰 정사각형 찾기

// https://programmers.co.kr/learn/courses/30/lessons/12905
//   가장 큰 정사각형 찾기
function solution(board) {
  var answer = 1;

  var lownum = board.length;
  var colnum = board[0].length;
  console.log(lownum, colnum);

  if (lownum == 1 || colnum == 1) {
    var maxRow = board.map(function (row) {
      return Math.max.apply(null, row);
    });
    var max = Math.max.apply(null, maxRow);

    return max;
  }

  var max = 0;

  for (var q = 1; q < board.length; q++) {
    for (var w = 1; w < board[0].length; w++) {
      if (board[q][w] == 0) {
        continue;
      }
      var arr = [board[q - 1][w - 1], board[q - 1][w], board[q][w - 1]];
      board[q][w] = Math.min.apply(null, arr) + 1;
      max = Math.max(max, board[q][w]);
    }
  }

  answer = max * max;

  //   console.log(maxRow, max);
  console.log(answer);
  return answer;
}

해설

• 2차원 배열이 입력으로 들어온다

• 2차월 연속된 1 이 이루는 가장 큰 정사각형의 넓이를 반환해야 한다

• 먼저 입력된 보드가 행과 열 어느 하나가 1인 경우 1또는 0을 반환한다

• 이제 1이 아닌 경우에 복잡해 지는데..

• 0과 1로만 이루어진 보드를 갱신해 나갈거다

• board[1][1] 부터 시작해서 이전 3개를 살펴볼것이다

• 이때 board[1][1]이 0 이면 패스한다. 1이면 ㄱㄱ

• 위, 왼쪽, 왼쪽 대각선위를 살펴서 가장 작은 숫자를 찾는다

• 그런다음에 board[1][1]에 가장 작은 숫자 + 1을 대입한다

• board[1][2] 로 이동해서 같은 것을 반복한다

• 그림으로 보면 이렇다

• step1] board[1][1] 일때

  

• step1] board[1][2] 일때

  

• 반복…

• 결과]

  

• 위 처럼 계속 갱신하고 보드에 마지막에 도달하면 끝이 난다

• 이후에 board 내에서 가장 높은 숫자를 찾는다. 그러면 3이라는 숫자를 얻을 수 있다

• 넓이를 반환하고 했으니까 3*3 해서 9를 반환하면 된다