프로그래머스 코딩테스트 연습 Level 2 - 가장 큰 정사각형 찾기 (JavaScript)

프로그래머스 코딩테스트 연습 Level 2 - 가장 큰 정사각형 찾기 (JavaScript)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중,

[가장 큰 정사각형 찾기] 문제를 JavaScript를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

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

예를 들어

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

제한사항

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

 

입출력 예

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

 

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

 

작성한 답

solution.js

function solution(board) {
    const row = board.length;
    const col = board[0].length;
    
    if (row < 2 || col < 2) return 1;
    
    for (let i = 1; i < row; i++) {
        for (let j = 1; j < col; j++) {
            if (board[i][j] === 1) {
                board[i][j] = Math.min(board[i][j - 1], board[i - 1][j], board[i - 1][j - 1]) + 1;
            }
        }
    }
    return Math.max(...board.reduce((ac, v) => [ ...ac, Math.max(...v) ], [])) ** 2;
}

 

설명

먼저 board의 행과 열 길이를 따로 뽑아둡니다.

 

그리고 과 열의 길이 중 하나라도 2보다 작으면 가로 세로 길이가 1보다 더 크게 만들어질 수 있는 정사각형은 없으므로 1을 반환합니다.

 

그렇지않을 경우,

가장 위쪽 행과 가장 왼쪽 열만을 제외한 다른 요소들을 반목분을 돌면서해당 요소가 1일 경우에만 해당 요소의 왼쪽, 위쪽, 왼쪽 위 대각선 방향의 숫자들 중 가장 작은 수에 1을 더한 수를 해당 요소의 값으로 변경합니다.이렇게 진행하게 되면 각 요소들이 가지는 값은 해당 요소 자리를 가장 오른쪽 아래에 두고 형성할 수 있는 정사각형의 최대 길이를 가지게 됩니다.

 

이해를 돕기위해 문제의 입출력 예 #1 번이 진행되는 과정을 그려봤습니다!

이렇게 진행되어 만들어진 board는,

[
    [0, 1, 1, 1],
    [1, 1, 2, 2],
    [1, 2, 2, 3],
    [0, 0, 1, 0]
]

위와 같이 됩니다.

 

그럼 이제 각 요소는 자신을 가장 오른쪽 아래에 두고 형성할 수 있는 정사각형의 최대 길이이므로,

2차원 배열 안의 가장 큰 수를 구하여 정사각형의 크기는 한변의 제곱이므로 해당 값을 제곱하여 반환하면 됩니다.

 

가장 큰 수를 구하기 위해 Math.max() 를 사용하는데 이차원 배열을 1차원으로 풀어낸 뒤, 전개연산자를 사용하여 사용하면 됩니다.

※ 2차원 배열을 1차원으로 풀어내는 방법에는 여러가지가 있는데,

저같은 경우 가장 간단한 방법인 flat() 을 사용했더니 정확도 검사에서는 통과하였지만 효율성 검사에서 시간 초과도 아닌 런타임 오류가 발생하였습니다.

그리고 reduce를 사용할때도 안에 Math.max를 적용해 가장 큰 값만 넣어준 것이 아닌 모든 값을 넣어주자 역시 런타임 오류가 발생했습니다.

정확하지는 않지만 아마도 Math.max() 안에 넣어 비교하는 숫자가 너무 많아서 런타임 오류가 발생하는 것으로 예상되었습니다.

그리하여 위와 같은 방법을 사용했으니,

map을 사용하셔도 좋고 각자가 편하신 방법을 사용하여 풀어낸다음 가장 큰 값을 구하시면 되겠습니다!

 

그렇게 구한 가장 큰 수를 제곱하여 반환하여 문제를 해결할 수 있습니다.

 

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.