문제링크
코딩테스트 연습 - 가장 큰 정사각형 찾기
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9
programmers.co.kr
접근 방법
문제를 살펴보면 패턴이 보인다.
1 1 1 1
1 1 => 1 2
1 1 1 1 1 1
1 1 1 1 2 2
1 1 1 => 1 2 3
이처럼 각 축을 x, y라 했을때 (x, y), (x+1, y), (x, y+1), (x+1, y+1)이 모두 1이면
(x+1, y+1)은 (x, y), (x+1, y), (x, y+1)의 값 + 1 이된다.
이를 통해 dp를 이용하여 문제를 풀었다.
주의점
dp를 board와 같은 크기로 설정하면 for문에서 범위 설정에 문제가 생긴다.
board의 행과 열을 +1씩 키운 뒤, dp(1,1) === board(0,0)이라는 생각을 갖고 풀이해야 범위에서 에러가 발생하지 않는다.
function solution(board)
{
var answer = 1234;
dp = Array.from({length : board.length+1}, () => new Array(board[0].length+1).fill(0))
let maxLen = 0;
for(let x = 1; x < board.length+1; x++){
for(let y = 1; y < board[0].length+1; y++){
if(board[x-1][y-1] === 1){
dp[x][y] = Math.min(dp[x-1][y-1], dp[x-1][y], dp[x][y-1]) + 1;
}
maxLen = maxLen > dp[x][y] ? maxLen : dp[x][y]
}
}
answer = Math.pow(maxLen, 2);
return answer;
}
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
[Javascript] 피로도 (87946) (0) | 2022.06.23 |
---|---|
[Javascript] 2 * n 타일링 (12900) (0) | 2022.06.22 |
[Javascript] 이진 변환 반복 (70129) (0) | 2022.06.20 |
[Javascript] 올바른 괄호 (12909) (0) | 2022.06.19 |
[Javascript] 다음 큰 숫자 (12911) (0) | 2022.06.18 |