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

📖 문제링크

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

문제 설명

1와 0로 채워진 표에서 만들 수 있는 가장 큰 정사각형의 크기를 반환해라

👨‍💻 문제풀이

필자가 푼 문제풀이

function solution(board) {
    let answer = 0;
    
    if (board.length < 2 && board[0].length < 2) return 1;
    
    for (let i = 1; i < board.length; i++) {
        for (let j = 1; j < board[i].length; j++) {
            if (board[i][j]) {
                const up = board[i - 1][j];
                const left = board[i][j - 1];
                const cross = board[i - 1][j - 1];
                board[i][j] = Math.min(up, left, cross) + 1;
                answer = Math.max(answer, board[i][j]);
            }
        }
    }
    return answer * answer;
}

이 문제는 DP의 맛보기 같은 문제였다.
일단 생각을 해야지 풀 수 있는 문제라고 생각한다.

필자는 처음에 1이 연속적으로 들어가있는 index들을 모아서 재귀함수로 비교하려고 했지만 그게 아니고 훨씬 간단한 방법이 있었다.

• 사각형에서 가장 오른쪽 밑에 있는 좌표에 가장 큰 정사각형을 만들 수 있는 길이를 저장한다.
• 좌표의 위쪽, 왼쪽, 대각선왼쪽위 총 이렇게 3점을 비교해 결정해준다.

그리고 answer와 계속 비교하면서 가장 큰 길이의 곱을 반환하면 답이 나온다.

2022.02.14