[Swift Algorithm] 가장 큰 정사각형 찾기 Programmers(Lv.2)

문제 설명

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

 

예를 들어

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

제한 조건

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

 

입출력 예

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

 

내 문제 풀이

func solution(_ board:[[Int]]) -> Int {
    var block = board
    var result = 0
    
    // 만약 주어진 행이나 열이 1일 경우엔 어차피 정사각형 넓이가 1보다 클 수 없음
    if board.count == 1 || board[0].count == 1 {
        result = 1
    }
    
    // 1행 1열부터 끝까지 반복문
    for i in 1..<board.count {
        for j in 1..<board[0].count {
            if board[i][j] == 1 {
                block[i][j] = min(block[i-1][j-1], block[i-1][j], block[i][j-1]) + 1
                result = result < block[i][j] ? block[i][j] : result
            }
        }
    }
    
    // result의 제곱 출력
    return result * result
}

• 처음엔 어떻게 풀어야할지 전혀 가늠이 안돼서,,ㅜㅜ 다른 블로그를 참고하여 풀었다.
  이 풀이의 진행 방식을 그림으로 그려보자. (입출력 예제 1)
  

  

  [1][1]부터 원소가 1일 때, 그 전 원소들(이 경우에는 [0][0], [0][1], [1][0]) 중 가장 작은 수를 더해준다.
  

  

  위의 경우에는 그 전 원소들이 0, 1, 1 이기 때문에 그 중 가장 작은 0을 더해주었다.
  
  이런 방식으로 모든 원소들을 하나 하나 계산해 나가면,
  

  

  위와 같이 정사각형이 될 수 있는 경우의 수 중, 가장 긴 한 변의 길이를 구할 수 있다.
• 위의 로직으로 구한 수들 중 가장 큰 수를 result 배열에 담아 마지막에 제곱하여 리턴해주었다.

 

💡 피드백

• 처음에 가장 큰 정사각형을 구하는 방법을 생각해내지 못했는데,,
  문제를 많이 풀어보면서 이런 저런 풀이방법들을 익히고,,
  스스로 다양한 풀이 방법을 만들 수 있도록 많이 공부해야할 것 같다.

 

---

 

🖍 [ 추가 ] 1주일 후 다시 풀어보기

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

    return answer * answer
}

• 저번에 공부한 덕분에 바로 로직을 생각해서 풀 수 있었다.
• 근데 다시 보니, 첫 번째 풀이에서 처리해주지 않은 예외 하나가 보여서 처리해주었다.
• 첫 번째 if문에서, 배열의 원소 중 1이 하나도 없을 수도 있기 때문에,, 배열의 가장 큰 수가 1이 아닐 경우 0을 리턴하도록 했다.
  얼마 전 공부한 flatMap을 사용하여 2차원 배열을 1차원으로 만들어주어 쉽게 가장 큰 수를 구할 수 있었다.
• 나머지 로직은 첫 번째 풀이와 유사하다.

 

---

 

문제

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