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

가장 큰 정사각형 찾기(level 2)

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

---

풀이

첫번째 시도

각각의 위치 값에 대해 박스 사이즈를 늘려가면서 최대 박스 사이즈와 비교하는 방식으로 최대 크기의 박스사이즈를 구했다. 테스트에서 답은 모두 맞았지만 효율성 테스트에서 모두 틀렸다.  기존에  계산한 내용을 저장해둬서 체크하는 과정을 추가해서 효율성을 개선해야겠다 생각이 들었다.

//max 값 찾기
//처음에 전부 0으로 감싸주기//
//pos가 1이면 function 돌리기//
//박스크기1,박스크기2일때 각각의 경우의 수를 체크한다
//각 경우의 수에 0이 하나라도 있다면 종료
//전부 1이고 maxSize보다 크다면 갱신후 다음 박스 사이즈로

function solution(board)
{
    let maxSize = 0;
    const map = Array.from(Array(board.length+2),()=>Array(board[0].length+2).fill(0));
    for(let i=1;i<=board.length;i++){
        for(let j=1;j<=board[0].length;j++){
            map[i][j] = board[i-1][j-1]
        }
    }
    function checkSize(x,y){
        let size = 0;
        let findHole = false;
        
        while(!findHole){
            size++;
            for(let i=x;i<x+size;i++){
                for(let j=y;j<y+size;j++){
                    if(map[i][j] === 0){
                        findHole = true;
                    }
                }
            }
            if(!findHole && size>maxSize){
                maxSize = size;
            }
        }
    }
    for(let i=1;i<map.length;i++){
        for(let j=1;j<map.length;j++){
            if(map[i][j]===1){
                checkSize(i,j);
            }
        }
    }
    //console.log(maxSize)
    return maxSize**2
}

 

두번째 시도

질문하기에서 파이썬을 통해 dp로 구현한 것을 참고하여 DP를 활용해서 효율성을 높여야 겠다고 생각이 들었다. DP는 특정 알고리즘이 아닌 풀이 방식이기 때문에 다음 두개의 조건이 충족되어야 한다.

1. 가장 작은문제를 정의할 수 있는가? 
2. 가장 작은 문제로 큰 문제를 해결할 수 있는 규칙이 있는가

반복문을 통해 돌리면서 각 위치에 가능한 최대 크기의 박스를 board배열에 넣고 기존에 있던 최대값과 현재 위치에서 가능한 최대 값을 비교하였다. 가장 작은 문제인 각 위치의 값과 그 값으로 계산할 수 있는 다음 값들의 규칙으로 dp를 구현할 수 있었다.

function solution(board)
{
    let maxSize = 0;
    for(let i =0;i<board.length;i++){
        for(let j=0;j<board[0].length;j++){
            if(i===0||j===0||board[i][j]===0){
                maxSize = Math.max(maxSize, board[i][j]);
                continue;
            }
            board[i][j] = Math.min(board[i-1][j],board[i][j-1],board[i-1][j-1])+1;
            maxSize = Math.max(board[i][j], maxSize);
        }
    }
    
    return maxSize**2
}

 

더 나은 로직 또는 클린 코드를 위한 피드백은 감사히 받겠습니다.