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

📝 문제

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

 

제한사항

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

🤔 나의 풀이

function solution(board) {
    let answer = 0;

    for(let i = 0; i < board.length - 1; i++) {
        let count = 0;
        for(let j = 0; j < board[0].length; j++) {
            let v = board[i][j];
            if(v === 1) count++;
            if(v === 1 && j === board[0].length - 1 || v === 0 && count > 0) {
                if(check(i,j,count)) answer = Math.max(answer,count);
                count = 0;
            }
        }
    }

    function check(i, j, count) { // i = 행, j = 열
        for(let k = i + 1; k < i + count; k++) {
            if(!board[k]) return false;
            if(board[k].slice(j-count,j).includes(0)) return false;
        }
        return true;
    }

    return answer*answer;
}

 
마땅한 풀이가 떠오르지 않아 완전 탐색으로 풀었다.
2중 포문 + check함수의 for문으로 대략 O(n^3)의 시간복잡도를 가져서 비효율적이다.
게다가 테스트코드도 모두 통과하지 못했다.
 

🔑 모범 풀이

다이나믹 프로그래밍을 사용해서 풀어야 하는 문제다.
해당 알고리즘 관련해서는 이미 포스팅을 했다.
 
[알고리즘] 다이나믹 프로그래밍 (동적 프로그래밍)

 

구현 과정

 

1. 동그라미 친 board[1][1]부터 시작해서 하늘색 부분만 순회한다.
2. 값의 왼쪽, 위쪽, 왼쪽 상단 대각선 값을 비교해 최소값 + 1을 해당 위치에 저장한다.
3. 순회를 끝마치고 모든 값 중, 최대값의 제곱을 반환한다.

 

코드

function solution(board) {

    if(board.length < 2 || board[0].length < 2) return 1;
    
    let answer = 0;
    
    for(let r = 1; r < board.length; r++) {
        for(let c = 1; c < board[0].length; c++) {
            if(board[r][c] === 0) continue;
            board[r][c] = Math.min(board[r-1][c-1], board[r-1][c], board[r][c-1]) + 1;
        }
        answer = Math.max(answer, ...board[r]);
    }
    
    return answer * answer;
}

 

• 정확도 테스트 결과

 

• 효율성 테스트

 

🤷‍♀️ 테스트케이스 오류 가능성

제한사항을 모두 따져보면 [[0],[0]] 나 [[0,0,0]] 같은 값이 주어질 수 있고, 결과값은 0이어야 한다.
하지만 이를 고려한 아래 풀이는 테스트 1을 통과하지 못한다. (조건을 삭제한 풀이)
문제에 오류가 있다고 판단된다. (다른 의견이 있다면 댓글 남겨주세요)

function solution(board) {

    let answer = 0;
    
    for(let r = 1; r < board.length; r++) {
        for(let c = 1; c < board[0].length; c++) {
            if(board[r][c] === 0) continue;
            board[r][c] = Math.min(board[r-1][c-1], board[r-1][c], board[r][c-1]) + 1;
        }
        answer = Math.max(answer, ...board[r]);
    }
    
    return answer * answer;
}

 

---

참고

velog.io/@diddnjs02