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

처리조건

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

풀이

y축은 board의 길이가 될 것이고 x축은 board[0]의 길이가 될 것이다. 만약 이 두개의 길이중 하나라도 2보다 작다면 최대 만들수 있는 정사각형은 1x1일 것이다. 또한 정사각형 크기는 1x1 2x2 3x3 으로 커진다는 것을 잘 기억하고 아래 그림을 확인해보자.

그림 처럼 1x1보다 큰 정사각형을 만드는 2x2부터 확인해야하므로 빨간색 1을 기준으로 왼쪽 왼쪽대각 위쪽의 숫자를 검사해서 모두가 1일때 2x2를 만들수 있고 2x2를 만들때마다 이를 자신빨간색기준 1이 2x2를 만들수 있는 값이라는 것을 기억시켜준다. 이후에 더 큰 3x3도 만들수 있는지 확인해볼 것이기 때문이다. 그리고 지금껏 2x2까지 만들수 있었다는 것을 기억시켜주기 위해 다른 변수에 현재 최대 2x2이다 라는것을 기억시켜둔다.

 

board[y][x]기준 왼쪽 위쪽 대각 왼쪽중 가장 작은 값을 찾아 +1 시켜준뒤 자신을 바꿔주면서 answer최대값도 바꿔주며 이동한다. 예를 들어 자신을 2로바꾸었고 다음 옆 1을 기준으로 왼쪽에 2 대각에 1 위에 1이 있어도 대 표에서는 0과1로만 구성되어 있고 0을 제외한 1,2는 모두 정사각형을 만드는 1로 생각해줘도 되며 단지 해당 정사각형이서 모두가 1이였다는 것을 알기위해 2로 바꿔 놓은것이다. 그래서 min을 통해 가장 작은 값을 찾는 것도 사실상 자신기준으로 왼쪽 대각 위쪽에 0이 있나 찾는다는 것이다.

 

아직은 이런 배열이나 좌표에서 규칙성이나 어떻게 로직을 구성해야 할 지 바로 떠오르진 않는다.. 계속 접근하다보면 쉬워지지 않을까 싶다.

 

function solution(board) {
  let answer = 0;

  if (board.length < 2 || board[0].length < 2) return 1;

  for (let y = 1; y < board.length; y++) {
    for (let x = 1; x < board[0].length; x++) {
      if (board[y][x] > 0) {
        let one = Math.min(board[y - 1][x - 1], board[y][x - 1], board[y - 1][x]);
        board[y][x] = one + 1;

        if (answer < board[y][x]) answer = board[y][x];
      }
    }
  }
  return answer * answer;
}