프로그래머스 JS [가장 큰 정사각형 찾기]
가장 큰 정사각형 찾기
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
| 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줄씩을 추가해주면 문제가 없지 않을까요.
이렇게 만들면...?
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;
}