[Level 2] 가장 큰 정사각형 찾기 + Swift

문제 링크

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

문제

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

입력

let board = [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]

출력

9

문제 풀이

1. board의 점 (row, column)(row>0, column>0)의
2. 해당 점의 좌측 상단(row-1, column-1), 좌측 (row-1, column), 상단 (row, column-1)의 최솟값을 구한다.
3. 기존 점에 최솟값을 더한다.
4. board의 최댓값은 정사각형의 길이로, 넓이를 return해야 하므로 제곱값을 반환한다.

func solution(_ board: [[Int]]) -> Int {
    var arrays = board
    var max = 0

    if board.count == 1 {
        return board[0].contains(1) ? 1 : 0
    }

    if  board[0].count == 1 {
        return board.flatMap {$0}.contains(1) ? 1 : 0
    }

    for row in 1..<board.count {
        for column in 1..<board[0].count {
            if arrays[row][column] == 1 {
                let min = [arrays[row-1][column-1], arrays[row-1][column], arrays[row][column-1]].min()
                arrays[row][column] += min ?? 0
                max = (max > arrays[row][column]) ? max : arrays[row][column]
            }
        }
    }

    return max * max
}