[Swift 알고리즘] 프로그래머스(Lv.2) - 가장 큰 정사각형 찾기

안녕하세요. 개발 중인 정주입니다.

 

오늘은 프로그래머스(Lv.2) - 가장 큰 정사각형 찾기 문제를 풀었습니다.

 

---

목차

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 과거 계산 내용을 저장해두는 DP 방법으로 풀 수 있습니다.

 

4개의 구역이 모두 0보다 크면 그중 최솟값 + 1을 대입합니다.

이 최소값 + 1은 정사각형 한 변의 길이입니다. +1 대신 넓이 공식을 적용해도 됩니다.

저는 한 변의 길이를 구해서 마지막에 제곱을 return 했습니다.

 

이때 1짜리 정사각형을 위해 i와 j가 0인 경우도 조건 처리를 해줘야 합니다.

 

설명만으로는 이해하기 힘드실 거니 코드와 함께 설명을 봐주세요!

 

---

전체 코드

import Foundation

func solution(_ board:[[Int]]) -> Int
{
    var answer:Int = 0
    var board = board
    
    for i in 0..<board.count {
        for j in 0..<board[0].count {
            if i == 0 || j == 0 {
                answer = max(answer, board[i][j])
            } else {
                if board[i-1][j-1] > 0 && board[i][j-1] > 0 && board[i-1][j] > 0 && board[i][j] > 0 {
                    board[i][j] = [board[i-1][j-1], board[i][j-1], board[i-1][j]].min()! + 1
                    answer = max(answer, board[i][j])
                }    
            }
        }
    }
    
    return answer * answer
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.