[프로그래머스] Lv2 - 가장 큰 정사각형 찾기

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

let width
let height
let rightAngles

function check(board,y,x,size){
  if(y >= height || x >= width) return false
  if(rightAngles[y][x] < size) return false
  return true
}

function getSize(board, y, x) {
  let size = 1;
  while (true) {
      if(y == height || x == width) return size-1
      if(rightAngles[y][x] < size) return size-1
      y++
      x++
      size+=1
  }
}


function solution(board)
{
    var answer = 0;
    
    height = board.length
    width = board[0].length
    
    
    rightAngles = Array.from(Array(height), () => Array(width).fill(0))
    
    for(let i = 0; i < height; i++){
        let cnt = 0
        for(let j = 0; j < width; j++){
            if(board[i][j] == 1) cnt++
            else cnt = 0
            rightAngles[i][j] = cnt
        }
    }
    
    for(let i = 0; i < width; i++){
        let cnt = 0
        for(let j = 0; j < height; j++){
            if(board[j][i] == 1) cnt++
            else cnt = 0
            rightAngles[j][i] = Math.min(rightAngles[j][i],cnt)
        }
    }
    
    
     for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
          if (board[i][j] == 1 && check(board,i+answer,j+answer,answer)) {
            let size = getSize(board, i, j);
            answer = Math.max(answer, size);
          }
        }
      }
    

    return answer**2;
}

Lv2 문제중에서 가장 시간을 많이 사용한것 같다.
풀이방법은 사이즈를 구하기전에 미리 각 1마다 자신의 왼쪽 그리고 위쪽의 1길이를 구해서 저장해놓는다. 이렇게 하는 이유는 정사각형의 최대 사이즈를 구할때 대각선 방향 '1'의 위쪽과 왼쪽의 길이만 알면 빠르게 정사각형을 확장해 나가면서 최대 사이즈를 알 수 있기 때문이다.(하단참조)

1 -> 1 2 -> 1 2 3 -> 1 2 3 4
     2 2    2 2 3    2 2 3 4
            3 3 3    3 3 3 4
                     4 4 4 4

이렇게 까지 했을 때 정답은 맞았으나 효율성 체크해서 자꾸 시간초과가 났다..
getSize함수에서 시간을 많이 잡아 먹는듯 했다.
그래서 사이즈를 구할 필요가 있을 경우에만(가지치기) getSize함수를 호출하기 위해서 check함수를 구현했다. check함수의 용도는 현재까지 최대 사이즈(answer)보다 1큰 위치에 정사각형을 구할 수 있는지 미리체크하였다.

시간복잡도는 최악의 경우 무려 O(N^3)이다.... 가지치기가 필수로 필요하다.