프로그래머스 가장 큰 정사각형 찾기 Swift

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

 

 

Foma's 풀이

문제풀이

이 문제는 동적계획법(Dynamic Programming)으로 풀어야 하는 문제입니다.

 

동적계획법에 대해서는 dojinkimm.github.io/algorithm/2019/10/17/dp-1.html 이곳을 참고해주세요!

Dynamic Programming(동적 계획법)이란?

간단하게 설명드리면 board안의 숫자를 차례로 돌면서 n과 같은 열에서 윗쪽 행의 수,자신보다 하나 앞선 열에서 윗쪽의 수, 자신과 같은 행에서 하나 앞선 수 즉,자신을 둘러싼 수 중 가장 작은 수를 n에게 더해주면 됩니다. 

 

그 다음 바뀐 n들중 가장 큰 숫자에 제곱을 해주시면 됩니다. 이와 같이 풀어주시면 가장 안쪽의 수는 정사각형의 행(열)을 알 수 있게 됩니다.

 

예시로 설명드리면 아래 표에서 가운데 숫자가 n이라면 빨간색이 되고 자신을 둘러싼 세개의 수는 파란색이 됩니다. 파란색인 숫자 중 가장 작은 수는 0이므로 빨간색인 1에 0을 더한다면 1이 되므로 n은 1 그대로 남습니다.

0	1	1
0	1	1
1	0	1

모든 수에 이것을 적용하면 이와 같이 변하고 이 중 가장 큰 수는 2이므로 2의 제곱은 4가 되서 가장 큰 정사각형의 넓이는 4가 됩니다.

0	1	1
0	1	2
1	0	1

코드설명

가장 먼저 findMin함수와 solution의 board값을 공유하기 위해 board를 복사한 값을 담을 변수를 만들어줍니다. - > var boardCopy = [[Int]]()

 

그 다음 solution을 보기 전에 아래에 있는 findMin함수부터 알아보겠습니다.

 

findMin은 인자값으로 n(현재의 수)과 row(열),line(행)을 가지며 정수를 반환하도록 되어있습니다.

-> func findMin(_ n:Int,_ row:Int,_ line:Int) -> Int {...)

 

반환값을 보면 n과 같은 열에서 윗쪽 행의 수 -> boardCopy[row][line-1]

 

자신보다 하나 앞선 열에서 윗쪽의 수 -> boardCopy[row-1][line-1],

 

자신과 같은 행에서 하나 앞선 수 중 가장 작은 수 -> boardCopy[row-1][line]

 

에서 가장 작은 값을 min() 메소드를 통해 반환하도록 되어있습니다. -> min(boardCopy[row-1][line],boardCopy[row-1][line-1],boardCopy[row][line-1])

 

solution을 살펴보면 n들 중 가장 큰 값을 저장할 변수를 만들어줍니다. -> var maxNum = 0

 

먼저 열이나 행이 1로 되어있는 보드는 정사각형이 1이 가장 크기 때문에 1을 반환해줍니다. - > if board.count == 1 || board.filter({$0.count > 1}).count == 0 { return 1 }

 

board안의 배열들을 1부터 차례로 for문을 이용해 탐색합니다. (1부터 탐색하는 이유는 0번째 행은 자신을 둘러싼 세개의 수를 구할 수가 없기 때문입니다.) - > for i in 1..<board.count {...}

 

그리고 바로 board안의 배열들의 안을 for문을 이용해 탐색합니다. -> for j in 1..<board[i].count {...}

 

만약 n이 0이 아니라면 (만약 0이라면 자신을 둘러싼 3개의 수를 구할 필요가 없음. ) n에 가장 작은 수를 더해주고 이것이 가장 큰 수라면 (max()메소드로 비교) maxNum을 바꿔줍니다.(n은 board[i][j] 열은 i 행은 j가 될 것입니다.)- > 

 if  boardCopy[i][j] != 0 {

                boardCopy[i][j] += findMin(board[i][j], i, j)

                maxNum = max(maxNum, boardCopy[i][j])

  }

 

board안의 다 탐색한 뒤 maxNum에 pow()메소드 사용하여 제곱한 값을 반환해줍니다.(pow()메소드는 인자값을 Double로 받습니다.) ->

return  Int(pow(Double(maxNum),2.0))

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

import Foundation   var boardCopy = [[Int]]()   func solution(_ board:[[Int]]) -> Int {     var maxNum = 0 boardCopy = board     if board.count == 1 || board.filter({$0.count > 1}).count == 0 {         return 1     }     for i in 1..<board.count {         for j in 1..<board[i].count {             if  boardCopy[i][j] != 0 {                 boardCopy[i][j] += findMin(board[i][j], i, j)                 maxNum = max(maxNum, boardCopy[i][j])             }         }     }     return  Int(pow(Double(maxNum),2.0)) }   func findMin(_ n:Int,_ row:Int,_ line:Int) -> Int {          return min(boardCopy[row-1][line],boardCopy[row-1][line-1],boardCopy[row][line-1]) } Colored by Color Scripter

새롭게 알게 된 것

n제곱을 구할 땐 pow(Double(n),Double(제곱할 수))를 사용하여 구할 수 있다.

 

동적계획법