[Swift] 코딩테스트 연습! Lv2. 가장 큰 정사각형 찾기

/* 가장 큰 정사각형 찾기

 - 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
 
 제한사항
 표(board)는 2차원 배열로 주어집니다.
 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
 표(board)의 값은 1또는 0으로만 이루어져 있습니다.
*/
// 성공!!
func solution111111111111(_ board:[[Int]]) -> Int {
    var max:Int = 0
    var zeroList:[[Int]] = []
    for i in 0...board.count-1 {
        if i+max < board.count {
            var jumpIndex = -1
            for j in 0...board[0].count-1 {
                if j+max < board[0].count {
                    if board[i][j] == 1 && j > jumpIndex && zeroList.filter({ $0[0] >= i && $0[0] <= i+max && $0[1] >= j && $0[1] <= j+max }).count == 0 {
                        var isStop = false
                        var isMax = false
                        while !isStop {
                            if i+max < board.count && j+max < board[0].count {
                                if !isMax {
                                    for k in i...i+max {
                                        for l in j...j+max {
                                            if board[k][l] == 0 {
                                                isStop = true
                                                zeroList.append([k,l])
                                                if l > jumpIndex {
                                                    jumpIndex = l
                                                }
                                                break
                                            }
                                        }
                                        if isStop {
                                            break
                                        }
                                    }
                                } else {
                                    for k in i...i+max-1 {
                                        if board[k][j+max] == 0 {
                                            isStop = true
                                            zeroList.append([k,j+max])
                                            if j+max > jumpIndex {
                                                jumpIndex = j+max
                                            }
                                            break
                                        }
                                    }
                                    if !isStop {
                                        for l in j...j+max {
                                            if board[i+max][l] == 0 {
                                                isStop = true
                                                zeroList.append([i+max,l])
                                                if l > jumpIndex {
                                                    jumpIndex = l
                                                }
                                                break
                                            }
                                        }
                                    }
                                }
                                if !isStop {
                                    isMax = true
                                    max += 1
                                }
                            } else {
                                isStop = true
                                break
                            }
                        }
                    }
                } else {
                    break
                }
            }
        } else {
            break
        }
    }
    return max*max
}

solution111111111111([[0, 0, 1, 1], [1, 1, 1, 1]])

// 2,3 실패
func solution11111111111(_ board:[[Int]]) -> Int {
    var max:Int = 0
    for i in 0...board.count-1 {
        if i+max < board.count {
            var jumpIndex = -1
            for j in 0...board[0].count-1 {
                if j+max < board[0].count {
                    if board[i][j] == 1 && j > jumpIndex {
                        var isStop = false
                        var isMax = false
                        while !isStop {
                            if i+max < board.count && j+max < board[0].count {
                                if !isMax {
                                    for k in i...i+max {
                                        for l in j...j+max {
                                            if board[k][l] == 0 {
                                                isStop = true
                                                if l > jumpIndex {
                                                    jumpIndex = l
                                                }
                                                break
                                            }
                                        }
                                        if isStop {
                                            break
                                        }
                                    }
                                } else {
                                    for k in i...i+max-1 {
                                        if board[k][j+max] == 0 {
                                            isStop = true
                                            if j+max > jumpIndex {
                                                jumpIndex = j+max
                                            }
                                            break
                                        }
                                    }
                                    if !isStop {
                                        for l in j...j+max {
                                            if board[i+max][l] == 0 {
                                                isStop = true
                                                if l > jumpIndex {
                                                    jumpIndex = l
                                                }
                                                break
                                            }
                                        }
                                    }
                                }
                                if !isStop {
                                    isMax = true
                                    max += 1
                                }
                            } else {
                                isStop = true
                                break
                            }
                        }
                    }
                } else {
                    break
                }
            }
        } else {
            break
        }
    }
    return max*max
}

solution11111111111([[0, 0, 1, 1], [1, 1, 1, 1]])

// 효울성 1,3 실패
func solution1111111111(_ board:[[Int]]) -> Int {
    var max:Int = 0
    var zeroList:[[Int]] = []
    for i in 0...board.count-1 {
        if i+max < board.count {
            var zeroFilterList = zeroList.filter({ $0[0] >= i && $0[0] <= i+max })
            for j in 0...board[0].count-1 {
                if j+max < board[0].count {
                    if board[i][j] == 1 && zeroFilterList.filter({ $0[1] >= j && $0[1] <= j+max }).count == 0 {
                        var isStop = false
                        var isMax = false
                        while !isStop {
                            if i+max < board.count && j+max < board[0].count {
                                if !isMax {
                                    for k in i...i+max {
                                        for l in j...j+max {
                                            if board[k][l] == 0 {
                                                isStop = true
                                                zeroList.append([k,l])
                                                break
                                            }
                                        }
                                        if isStop {
                                            break
                                        }
                                    }
                                } else {
                                    for k in i...i+max-1 {
                                        if board[k][j+max] == 0 {
                                            isStop = true
                                            zeroList.append([k,j+max])
                                            break
                                        }
                                    }
                                    if !isStop {
                                        for l in j...j+max {
                                            if board[i+max][l] == 0 {
                                                isStop = true
                                                zeroList.append([i+max,l])
                                                break
                                            }
                                        }
                                    }
                                }
                                if !isStop {
                                    isMax = true
                                    max += 1
                                }
                            } else {
                                isStop = true
                                break
                            }
                        }
                    }
                } else {
                    break
                }
            }
        } else {
            break
        }
    }
    return max*max
}

solution1111111111([[0, 0, 1, 1], [1, 1, 1, 1]])

// 효율성 1 탈락
func solution111111111(_ board:[[Int]]) -> Int {
    var max:Int = 0
    var zeroList:[[Int]] = []
    for i in 0...board.count-1 {
        if i+max < board.count {
            for j in 0...board[0].count-1 {
                if j+max < board[0].count {
                    if board[i][j] == 1 && zeroList.filter({ $0[0] >= i && $0[0] <= i+max && $0[1] >= j && $0[1] <= j+max }).count == 0 {
                        var isStop = false
                        var isMax = false
                        while !isStop {
                            if i+max < board.count && j+max < board[0].count {
                                if !isMax {
                                    for k in i...i+max {
                                        for l in j...j+max {
                                            if board[k][l] == 0 {
                                                isStop = true
                                                zeroList.append([k,l])
                                                break
                                            }
                                        }
                                        if isStop {
                                            break
                                        }
                                    }
                                } else {
                                    for k in i...i+max-1 {
                                        if board[k][j+max] == 0 {
                                            isStop = true
                                            zeroList.append([k,j+max])
                                            break
                                        }
                                    }
                                    if !isStop {
                                        for l in j...j+max {
                                            if board[i+max][l] == 0 {
                                                isStop = true
                                                zeroList.append([i+max,l])
                                                break
                                            }
                                        }
                                    }
                                }
                                if !isStop {
                                    isMax = true
                                    max += 1
                                }
                            } else {
                                isStop = true
                                break
                            }
                        }
                    }
                } else {
                    break
                }
            }
        } else {
            break
        }
    }
    return max*max
}

solution111111111([[0, 0, 1, 1], [1, 1, 1, 1]])

// 효율성 2,3 탈락
func solution11111111(_ board:[[Int]]) -> Int {
    var max:Int = 0
    for i in 0...board.count-1 {
        if i+max < board.count {
            for j in 0...board[0].count-1 {
                if j+max < board[0].count {
                    if board[i][j] == 1 {
                        var isStop = false
                        var isMax = false
                        while !isStop {
                            if i+max < board.count && j+max < board[0].count {
                                if !isMax {
                                    for b in board[i...i+max] {
                                        for k in j...j+max {
                                            if b[k] == 0 {
                                                isStop = true
                                                break
                                            }
                                        }
                                        if isStop {
                                            break
                                        }
                                    }
                                } else {
                                    for b in board[i...i+max-1] {
                                        if b[j+max] != 1 {
                                            isStop = true
                                            break
                                        }
                                    }
                                    if !isStop {
                                        for k in j...j+max {
                                            if board[i+max][k] == 0 {
                                                isStop = true
                                                break
                                            }
                                        }
                                    }
                                }
                                if !isStop {
                                    isMax = true
                                    max += 1
                                }
                            } else {
                                isStop = true
                                break
                            }
                        }
                    }
                } else {
                    break
                }
            }
        } else {
            break
        }
    }
    return max*max
}

solution11111111([[0, 0, 1, 1], [1, 1, 1, 1]])
solution11111111([[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]])

func solution1111111(_ board:[[Int]]) -> Int {
    var max:Int = 0
    for i in 0...board.count-1 {
        for j in 0...board[0].count-1 {
            if board[i][j] == 1 {
                var isStop = false
                while !isStop {
                    if i+max < board.count && j+max < board[0].count {
                        for k in 0...max {
                            for l in 0...max {
                                if board[i+k][j+l] == 0 {
                                    isStop = true
                                    break
                                }
                            }
                            if isStop {
                                break
                            }
                        }
                        if !isStop {
                            max += 1
                        }
                    } else {
                        isStop = true
                    }
                }
            }
        }
    }
    return max*max
}

solution1111111([[0, 0, 1, 1], [1, 1, 1, 1]])
solution1111111([[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]])

func solution111111(_ board:[[Int]]) -> Int {
    var maxOneOne:Int = 0
    var boardFilter:[Int] = board.map({
        var maxOne:Int = 0
        var count:Int = 0
        for i in 0...$0.count-1 {
            if $0[i] == 1 {
                count += 1
            } else {
                if maxOne < count {
                    maxOne = count
                }
                count = 0
            }
        }
        if maxOne < count {
            maxOne = count
        }
        if maxOneOne < maxOne {
            maxOneOne = maxOne
        }
        return maxOne
    });
    if maxOneOne == 0 || maxOneOne == 1 {
        return maxOneOne
    }
    if board.count == 1 || board[0].count == 1 {
        return 1
    }
    var max:Int = min(boardFilter.count, maxOneOne)+1
    for _ in 0...max-3 {
        max -= 1
        if boardFilter.filter({ $0 >= max }).count >= max {
            for i in 0...board.count-max {
                if boardFilter[i] >= max {
                    var zeroLow:Int = -1
                    for j in 0...board[0].count-max {
                        if zeroLow < j {
                            var isS = true
                            for k in i...i+max-1 {
                                for l in j...j+max-1 {
                                    if board[k][l] == 0 {
                                        isS = false
                                        zeroLow = l
                                        break
                                    }
                                }
                                if !isS {
                                    break
                                }
                            }
                            if isS {
                                return max*max
                            }
                        }
                    }
                }
            }
        }
    }
    return 1
}

solution111111([[0, 0, 1, 1], [1, 1, 1, 1]])
solution111111([[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]])

func solution11111(_ board:[[Int]]) -> Int {
    if board.count == 0 {
        return 0
    }
    var boardFilter:[Int] = board.map({
        return $0.map { String($0) }.joined().components(separatedBy: "0").sorted{
            $0.count > $1.count
        }[0].count
    })
    var boardFilterSorted = boardFilter.sorted(by: >)
    if boardFilterSorted[0] == 0 || boardFilterSorted[0] == 1 {
        return boardFilterSorted[0]
    }
    if board.count == 1 || board[0].count == 1 {
        return 1
    }
    var max:Int = min(boardFilter.count, boardFilterSorted[0])+1
    for _ in 0...max-3 {
        max -= 1
        for i in 0...board.count-max {
            if boardFilter[i] >= max {
                var zeros:[Int] = []
                for j in 0...board[0].count-max {
                    if zeros.count == 0 || zeros.last! < j  {
                        var isS = true
                        for k in i...i+max-1 {
                            for l in j...j+max-1 {
                                if board[k][l] == 0 {
                                    isS = false
                                    zeros.append(l)
                                    break
                                }
                            }
                            if !isS {
                                break
                            }
                        }
                        if isS {
                            return max*max
                        }
                    }
                }
            }
        }
    }
    return 1
}

solution11111([[0, 0, 1, 1], [1, 1, 1, 1]])
solution11111([[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]])

// 27.90
func solution1111(_ board:[[Int]]) -> Int {
    if board.count == 0 {
        return 0
    }
    var boardFilter:[Int] = board.map({
        var maxOne:Int = 0
        var count:Int = 0
        for i in 0...$0.count-1 {
            if $0[i] == 1 {
                count += 1
            } else {
                if maxOne < count {
                    maxOne = count
                }
                count = 0
            }
        }
        if maxOne < count {
            maxOne = count
        }
        return maxOne
    });
    var boardFilterSorted = boardFilter.sorted(by: >)
    if boardFilterSorted[0] == 0 {
        return 0
    }
    if board.count == 1 || board[0].count == 1 {
        return 1
    }
    var max:Int = min(boardFilter.count, boardFilterSorted[0])+1
    for _ in 0...max-3 {
        max -= 1
        for i in 0...board.count-max {
            if boardFilter[i] >= max {
                var zeros:[Int] = []
                for j in 0...board[0].count-max {
                    if zeros.count == 0 || zeros.last! < j  {
                        var isS = true
                        for k in i...i+max-1 {
                            for l in j...j+max-1 {
                                if board[k][l] == 0 {
                                    isS = false
                                    zeros.append(l)
                                    break
                                }
                            }
                            if !isS {
                                break
                            }
                        }
                        if isS {
                            return max*max
                        }
                    }
                }
            }
        }
    }
    return 1
}

solution1111([[0, 0, 1, 1], [1, 1, 1, 1]])
solution1111([[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]])

func solution111(_ board:[[Int]]) -> Int {
    if board.count == 0 {
        return 0
    }
    var boardFilter = board.map({ $0.filter{ $0 == 1 }.count });
    if boardFilter.filter({ $0 > 0 }).count == 0 {
        return 0
    }
    if board.count == 1 || board[0].count == 1 {
        return 1
    }
    var max:Int = min(board.count, board[0].count)+1
    for _ in 0...max-3 {
        max -= 1
        for i in 0...board.count-max {
            if boardFilter[i] >= max &&
                board[i].map({ String($0) }).joined().contains(String(repeating: "1", count: max)) {
                var zeros:[Int] = []
                for j in 0...board[0].count-max {
                    if zeros.count == 0 || zeros.last! < j  {
                        var isS = true
                        for k in i...i+max-1 {
                            for l in j...j+max-1 {
                                if board[k][l] == 0 {
                                    isS = false
                                    zeros.append(l)
                                    break
                                }
                            }
                            if !isS {
                                break
                            }
                        }
                        if isS {
                            return max*max
                        }
                    }
                }
            }
        }
    }
    return 1
}

solution111([[0, 0, 1, 1], [1, 1, 1, 1]])
solution111([[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]])

func solution11(_ board:[[Int]]) -> Int {
    if board.count == 0 {
        return 0
    }
    var boardFilter = board.filter({ $0.filter{ $0 == 1 }.count > 0 }).sorted{ $0.count > $1.count };
    if boardFilter.count == 0 {
        return 0
    }
    if board.count == 1 || board[0].count == 1 {
        return 1
    }
    var max:Int = min(boardFilter.count, boardFilter[0].count)+1
    for _ in 0...max-3 {
        max -= 1
        for i in 0...board.count-max {
            if board[i].map({ String($0) }).joined().contains(String(repeating: "1", count: max)) {
                var zeros:[Int] = []
                for j in 0...board[0].count-max {
                    if zeros.count == 0 || zeros.last! < j  {
                        var isS = true
                        for k in i...i+max-1 {
                            for l in j...j+max-1 {
                                if board[k][l] == 0 {
                                    isS = false
                                    zeros.append(l)
                                    break
                                }
                            }
                            if !isS {
                                break
                            }
                        }
                        if isS {
                            return max*max
                        }
                    }
                }
            }
        }
    }
    return 1
}

solution11([[0, 0, 1, 1], [1, 1, 1, 1]])
solution11([[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]])

func solution1(_ board:[[Int]]) -> Int {
    if board.count == 0 {
        return 0
    }
    if board.filter({ $0.filter{ $0 == 1 }.count > 0 }).count == 0 {
        return 0
    }
    if board.count == 1 || board[0].count == 1 {
        return 1
    }
    var max:Int = min(board.count, board[0].count)+1
    for _ in 0...max-3 {
        max -= 1
        for i in 0...board.count-max {
            if board[i].map({ String($0) }).joined().contains(String(repeating: "1", count: max)) {
//            if board[i].filter({ $0 == 1 }).count >= max {
                for j in 0...board[0].count-max {
                    var isS = true
                    for k in i...i+max-1 {
//                        if board[k][j...j+max-1].contains(0) {
//                            isS = false
//                            break
//                        }
                        for l in j...j+max-1 {
                            if board[k][l] == 0 {
                                isS = false
                                break
                            }
                        }
                        if !isS {
                            break
                        }
                    }
                    if isS {
                        return max*max
                    }
                }
            }
        }
    }
    return 1
}