[프로그래머스/Swift] 12905번 - 가장 큰 정사각형 찾기

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12905

💡 구현 아이디어

• 현재 위치에서 넓이는 왼쪽 대각선 위, 위, 왼쪽의 영향을 받는다
• 3곳중 가장 작은 값에 +1을 한 값이 현재 위치에서 만들 수 있는 정사각형의 길이

💻 코드

• DP를 활용

import Foundation

func solution(_ board: [[Int]]) -> Int {
    var answer: Int = 0
    
    var checkBoard: [[Int]] = [[Int]](
        repeating: [Int](
            repeating: 0,
            count: board[0].count
        ),
        count: board.count
    )
    
    // 초기값 생성
    for i in 0..<board.count {
        checkBoard[i][0] = board[i][0]
        answer = max(answer,checkBoard[i][0])
    }
    for i in 0..<board[0].count {
        checkBoard[0][i] = board[0][i]
        answer = max(answer,checkBoard[0][i])
    }
    
    for y in 1..<board.count {
        for x in 1..<board[0].count {
            if board[y][x] == 1 {
                let a = checkBoard[y-1][x-1]
                let b = checkBoard[y-1][x]
                let c = checkBoard[y][x-1]
                checkBoard[y][x] = min(min(a,b),c) + 1   
                answer = max(answer,checkBoard[y][x])
            }
        }
    }
    return answer*answer
}

❌ 틀린 이유 및 틀린 부분

• 정확성은 100이 나왔지만, 효율성에서 0점이 나온 코드 (브루트포스 사용)

import Foundation

func solution(_ board: [[Int]]) -> Int {
    
    var answer: Int = 0
    let height: Int = board.count
    let width: Int = board[0].count
    
    func calLength(x0: Int, y0: Int) -> Int {
        let minLength = min(width, height)
        let maxLength = max(x0, y0)
        // 이후가 전부 1이어도 그 넓이가 이전에 구한 넓이보다 작을거같으면 바로 반환
        if answer > (minLength-maxLength) * (minLength-maxLength) {
            return -1
        }
        
        var x = x0+1
        var y = y0+1
        var length = 1
        while x < width && y < height {
            // 가로 확인
            for i in x0...x {
                if board[y][i] != 1 {
                    return length
                }
            }
            // 세로 확인
            for i in y0..<y {
                if board[i][x] != 1 {
                    return length
                }
            }
            x += 1
            y += 1
            length += 1
        }
        return length
    }
    
    for y in 0..<board.count {
        for x in 0..<board[0].count {
            if board[y][x] == 1 {
                let len = calLength(x0: x, y0: y)
                answer = max(len*len, answer)
            }
        }
    }

    return answer
}

⏳ 시간 복잡도

O(N) : 모든 칸을 한번씩만 확인

📌 풀이 또는 기억할 정보

• 효율성이 아주 많이 괴롭힌 문제 : answer = max(answer,checkBoard[y][x])를 현재 위치에서 하지말고 checkBoard를 다 구하고 다시 접근하는 순간! 시간초과가 나버린다..