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

문제 번호

코딩테스트 연습 - 가장 큰 정사각형 찾기

 

 

알고리즘 분류

DP

 

문제 풀이

 처음 풀이는 DP를 사용하지 않았었다. 주어진 board 배열에서 1을 발견할때마다 그 점을 왼쪽 상단 모서리로 하여 만들 수 있는 가장 큰 정사각형의 크기를 구하여 답으로 반환했었다.

 그러나 그렇게 풀이를 진행 할 경우 시간초과에 걸리게 된다. 따라서 해당 문제는 DP 알고리즘으로 해결하는 것이 맞다고 판단된다.

 

 우선 주어진 board 배열보다 1행이 추가된 2차원 배열을 생성한다.

    const col = board[0].length;
    const row = board.length;
    let dp = new Array(row+1).fill(0,0,row+1);
    for(let i=0; i<row+1; i++){
        dp[i] = new Array(col+1).fill(0,0,col+1);
    }
    
    for(let i=0; i<row; i++){
        for(let j=0; j<col; j++){
            dp[i+1][j+1] = board[i][j];
        }
    }

1행을 추가한 이유는 DP 배열의 모든 칸에 대해서 같은 알고리즘을 적용시키기 위해서이다.

 

 이제 DP 배열을 1행1열 부터 끝까지 탐색하면서 해당 칸이 0 이 아닐경우 알고리즘을 적용시킨다.

적용 시킬 알고리즘은 다음과 같다.

 

 현재 i행 j열에 있을때 바로 위 오른쪽(i-1, j-1)과 바로 위(i-1, j) 와 같은 행 왼쪽(i, j-1) 이렇게 3칸 중 가장 작은 값을 찾아서 그 값에 1을 더한 값을 i행 j열의 값으로 삼는다.

    for(let i=1; i<=row; i++){
        for(let j=1; j<=col; j++){
            if(dp[i][j] !== 0){
                let min = dp[i-1][j];
                min = min < dp[i-1][j-1] ? min : dp[i-1][j-1];
                min = min < dp[i][j-1] ? min : dp[i][j-1];        
                dp[i][j] = min + 1;
                if(dp[i][j] > max)
                    max = dp[i][j];
            }                
        }
    }

 dp배열의 내용을 채우면서 가장 큰 값이 나오면 변수 max에 기억해 둔다.

 

 좀 더 자세한 내용은 다음의 블로그에 그림과 함께 나와있다.

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

 

마지막으로  정사각형의 넓이는 (한변의 길이)^2 이므로 max^2를 return 하면 된다.

return max**2;

 

전체코드

function solution(board)
{
    let max = 0;
    const col = board[0].length;
    const row = board.length;
    let dp = new Array(row+1).fill(0,0,row+1);
    for(let i=0; i<row+1; i++){
        dp[i] = new Array(col+1).fill(0,0,col+1);
    }
    
    for(let i=0; i<row; i++){
        for(let j=0; j<col; j++){
            dp[i+1][j+1] = board[i][j];
        }
    }
    
    for(let i=1; i<=row; i++){
        for(let j=1; j<=col; j++){
            if(dp[i][j] !== 0){
                let min = dp[i-1][j];
                min = min < dp[i-1][j-1] ? min : dp[i-1][j-1];
                min = min < dp[i][j-1] ? min : dp[i][j-1];        
                dp[i][j] = min + 1;
                if(dp[i][j] > max)
                    max = dp[i][j];
            }                
        }
    }
    return max**2;
}

특이사항

 DP는 개념은 알아도 항상 문제에 적용시키가 쉽지 않은것 같다.

현 상태를 만들기 위해서 이전 값들을 어떻게 활용해야 하는지를 찾아야하는데 그 값들의 계산식이나 어떤 값을 기준으로 잡아야 하는지 등이 헷깔린다.

 이번 문제와 같이 2차원 배열을 사용하여 계산하는 문제들도 자주 보이므로 기억해두도록 하자.