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

가장 큰 정사각형 찾기

프로그래머스

 

 

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

 

문제요약: 0과 1로 이루어진 이차원 배열 속에서 1로 이루어진 가장 큰 정사각형의 크기를 구하시오.

---

문제 풀이 순서

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

이중 for 문을 이용해서 배열을 한 칸씩 돌며

 

빨간색 지점을 기준으로 

board[i][j] && 

=> 빨간색 지점이 1인지 확인한다.

board[i - 1][j - 1] > 0 && board[i - 1][j] > 0 && board[i][j - 1] > 0

x -1 좌표가 

y-1좌표가

x-1,y-1좌표가 

=> 1보다 큰지 확인한다.

 

 

전부 다 1보다 크면 정사각형이라는 뜻이므로

=> 네 칸 중에서 가장 작은 수만큼 빨간색 지점에 더한다.

 

[ 0, 1, 1, 1 ]
[ 1, 1, 2, 1 ] <<< 이렇게 바뀐다.
[ 1, 1, 1, 1 ]
[ 0, 0, 1, 0 ]

 

전부 다 실행하면

 

[ 0, 1, 1, 1 ]
[ 1, 1, 2, 2 ]
[ 1, 2, 2, 3 ]
[ 0, 0, 1, 0 ]

 

=> 3이 생기는데, 현재 숫자가 지금껏 나온 숫자 중 가장 큰 숫자임을 표시한다.

        if (highNum < board[i][j]) {
          highNum = board[i][j];
        }

 

 

가장 큰 정사각형의 넓이에 제곱한 값(3**2)을 반환하면 된다.

  let highNum = 1;

  for (let i = 1; i < board.length; i++) {
    for (let j = 1; j < board[0].length; j++) {
      if (board[i][j] && board[i - 1][j - 1] > 0 && board[i - 1][j] > 0 && board[i][j - 1] > 0) {
        board[i][j] += Math.min(board[i - 1][j], board[i][j - 1], board[i - 1][j - 1]);
        if (highNum < board[i][j]) {
          highNum = board[i][j];
        }
      }
    }
  }
 
  return highNum ** 2;

 

1칸 짜리 배열은 그럼 어떻게 구하나요?

  if (board.length === 1) {
    if (board[0].indexOf(1) === -1) {
      return 0;
    }
    return 1;
  }
  if (board[0].length === 1) {
    for (let i = 0; i < board.length; i++) {
      if (!board[i]) {
        return 0;
      }
      return 1;
    }
  }

=> 1을 찾아서 없으면 0을 반환하도록 예외처리 해주었다.

 

 

 

아니 그러면 전부 다 0인 경우는 어떻게 구하나요?

  let sum = 0;

  board.forEach((el) => {
    el.forEach((el2) => {
      sum += el2;
    });
  });

  if (sum === 0) {
    return 0;
  }

=> 다 더해서 0인 경우 0을 반환하도록 했다.

=> let highNum = 1 이 1부터 시작하도록 하면 2x2 이상의 배열에서는 최소 1을 반환하게 된다.

 

 

그런데 예외가 많아지니 코드가 너무 길다.

배열 자체를 이렇게 예외처리 하지 않고도 판단할 수 있도록

배열의 왼쪽과 위쪽에 1줄씩을 추가해주면 문제가 없지 않을까요.

[ 0, 0, 0, 0 ,0 ]

[ 0, 0, 1, 1, 1 ]

[ 0, 1, 1, 2, 2 ]

[ 0, 1, 2, 2, 3 ]

[ 0, 0, 0, 1, 0 ]

이렇게 만들면...?

 

 

  board.unshift(Array(board[0].length).fill(0));
=> board의 첫 배열의 길이만큼 0을 채워 맨 앞에 넣고,
  for (let i = 0; i < board.length; i++) {
    board[i].unshift(0);
  }
=> 각 배열에 0을 앞에 넣어줍니다.

 

 

 

 

전체 코드

function solution(board) {
  let sum = 0;

  board.forEach((row) => {
    row.forEach((column) => (sum += column));
  });

  if (sum === 0) return 0;

  board.unshift(Array(board[0].length).fill(0));
  for (let i = 0; i < board.length; i++) {
    board[i].unshift(0);
  }

  let highNum = 1;

  for (let i = 1; i < board.length; i++) {
    for (let j = 1; j < board[0].length; j++) {
      if (board[i][j] && board[i - 1][j - 1] > 0 && board[i - 1][j] > 0 && board[i][j - 1] > 0) {
        board[i][j] += Math.min(board[i - 1][j], board[i][j - 1], board[i - 1][j - 1]);
        if (highNum < board[i][j]) {
          highNum = board[i][j];
        }
      }
    }
  }

  return highNum ** 2;
}