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

사용 언어 : javascript
해결 날짜 : 2022-12-18
해결 방법 :
- dp를 활용해 문제 해결
  - board의 행, 열보다 1씩 큰 dp 배열 생성 및 초기화
  - board를 돌며 값이 1인 경우,
    - dp에서 해당 값을 좌측 위, 좌측, 위 중 가장 작은 값 + 1로 업데이트
    - 정사각형 한 변의 길이 최대값 업데이트
회고 :
- 처음에 정사각형 한 변의 길이의 최대값 업데이트 하는 로직을 작성하지 않고, 마지막에 dp에 flat()를 적용하여 1차원 배열로 만든 뒤 최대값을 찾는 방식을 사용했다.
- 그러나 효율성 테스트에서 런타임 에러가 발생했고, 아마 dp의 크기가 커질 경우 flat()이나 Math.max()에서 시간이 많이 소요되는 것이라 생각된다.
- 따라서 반복문에서 사전 정의한 max 값을 업데이트하는 방식으로 문제 해결

코드

function solution(board) {
  const dp = Array.from({ length: board.length + 1 }, () =>
    Array.from({ length: board[0].length + 1 }, () => 0),
  );
  let max = 0;

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] === 1) {
        dp[i + 1][j + 1] = Math.min(dp[i][j], dp[i + 1][j], dp[i][j + 1]) + 1;
        max = Math.max(max, dp[i + 1][j + 1]);
      }
    }
  }

  return max ** 2;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges