[JS] [Programmers] 가장 큰 정사각형 찾기

프로그래머스

• 프로그래머스 코딩 테스트 연습 Level 2 문제입니다.
• 나의 풀이는 효율성을 통과하지 못했습니다. 정답이 궁금하신 분들은 다른 사람의 풀이 부분을 참고해주시기 바랍니다!

 

나의 풀이

---

function solution(board) {
    let answer = 0;

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[i].length; j++) {

            if (board[i][j] == 1 && answer < (board.length - i + 1) ** 2) {
                answer = Math.max(answer, checkSquare(board, i, j));
            }

        }
    }
    return answer;
}

function checkSquare(board, i, j) {
    let checkI = i + 1;
    let checkJ = j + 1;
    let result = 1;

    while (checkI < board.length && checkJ < board[i].length) {

        for (let tempI = i; tempI <= checkI; tempI++) {
            for (let tempJ = j; tempJ <= checkJ; tempJ++) {
                if (board[tempI][tempJ] == 0) {
                    return result;
                }
            }
        }

        result = (checkI - i + 1) * (checkJ - j + 1);
        checkI++
        checkJ++
    }

    return result;
}

let board = [[0, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [0, 0, 1, 0]];
console.log(solution(board));

 

풀이 순서

---

1. 주어진 2차원 배열을 처음부터 끝까지 검사하면서 값이 1인 경우 해당 값의 위치를 정사각형의 좌측 상단 꼭짓점으로 보고 최대 정사각형의 크기를 구하는 방식으로 풀었습니다.
   
   
   1. checkSquere() 함수를 통해 현재 값의 위치를 정사각형의 좌측 상단 꼭짓점으로 하는 최대 정사각형의 넓이를 구했습니다.
   2. 현재 위치( i, j ) 부터 한 칸씩 범위를 넓혀가며 만약 해당 범위의 값들이 모두 1인 경우 정사각형이기 때문에 다음 범위를 검사했고, 1이 아니라면 현재 정사각형의 넓이를 리턴했습니다.
   3. 정사각형의 넓이는 최종적으로 나온 위치 ( checkI, checkJ )에서 탐색을 시작한 위치 ( i, j ) 까지의 거리를 구해 곱해줬습니다. 

 

😅 제가 푼 방법으로 제출하면 정확성도 테스트는 모두 통과하지만 효율성 테스트는 실패합니다.. ㅠㅠ

 

 

• 문제를 풀면서도 효율성 면에서 좋지 않다는 걸 알고 있었기 때문에 효율성 테스트를 통과하지 못하는 것이 당황스럽지는 않았습니다.
• 효율성 테스트를 통과하기 위해 몇 가지 조건을 추가해봤는데.. 동일하게 통과를 하지 못했습니다. 제가 추가한 검사 조건은 아래와 같습니다.
  
  
  1. 현재 구한 정답 값이 앞으로 검사할 영역의 최댓값보다 작은 경우만 검사하기.
  2. 현재 위치부터 ++ 해주면서 검사하는 것이 아닌 최대 위치부터 -- 해주면서 검사하기.

• 이처럼 다른 방법을 시도해봤지만 통과하지 못하여 다른 분들의 풀이를 참고했습니다 ㅠㅠ.. 아래 [ 다른 사람의 풀이 ] 부분을 읽어주시면 감사하겠습니다.

 

다른 사람의 풀이

---

문제의 이해와 풀이

 

다이나믹 프로그래밍(DP) 문제입니다.

 

• 4칸의 정사격형이 될 때는 현재 위치에서 왼쪽 상단, 위쪽, 왼쪽의 값이 1인 경우입니다.
• 만약 한 곳이라도 1이 아니라면 정사각형이 되지 못합니다.

• 9칸의 정사각형이 될 때는 위 이미지와 같이 현재 위치에서 화살표에 위치한 값이 모두 1 이어야 정사각형이 됩니다.

 

👉 그렇다면 이런 방법으로 현재 위치에서 좌측, 그 좌측의 좌측.. 좌측 상단, 그 좌측 상단의 조착 상단... 의 위치를 검사한다면 똑같이 효율성 테스트를 통과하지 못할 것입니다. 위 정사각형의 될 때의 이미지를 잘 생각해보면 문제 풀이의 핵심은 아래와 같습니다.

 

1. 만약 행 또는 열이 1 이면 가장 큰 정사각형의 넓이는 1 입니다.
2. 루프를 돌며 만약 자신의 위치(현재 인덱스)의 값이 1 이상일 경우 왼쪽상단(↖︎), 위쪽(↑), 왼쪽(←)의 최솟값을 구한 후 자신의 위치에 최솟값 + 1 의 값을 넣어줍니다.
3. 루프가 종료되었을 때 배열에서 가장 큰 값이 정사각형의 한 변의 길이입니다.
4. 따라서 가장 큰 값 제곱한 값이 최대 정사각형의 넓이입니다

[ 풀이 과정에 도움이 되는 이미지 ]

function solution(board) {
    let answer = 0;

    if (board.length == 1 || board[0].length == 1) {
        return 1
    }

    for (let i = 1; i < board.length; i++) {
        for (let j = 1; j < board[i].length; j++) {

            if (board[i][j] != 0) {
                let minValue = Math.min(
                    board[i - 1][j - 1], //좌측 상단
                    board[i][j - 1], //좌측
                    board[i - 1][j], //위쪽
                );

                board[i][j] = minValue + 1;

                answer = Math.max(answer, board[i][j]);
            }

        }
    }

    return answer ** 2

}

 

 

🔗 참고한 글

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