[programmers/Swift] 가장 큰 정사각형 찾기

programmers.co.kr - 코딩테스트연습 - Lv.2 - 연습문제 - 가장 큰 정사각형 찾기

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

Constraints :

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

 

Solution.swift :

//
//  Created by Yongwoo Marco on 2022/05/08.
//  Copyright © 2022 Yongwoo Marco Kim. All rights reserved.
//

func solution(_ board:[[Int]]) -> Int {
    var maxSize = 0, check = board
    
    if board[0].filter({ $0 > 0}).count > 0 || board.filter({ $0[0] > 0 }).count > 0 {
        maxSize = 1
    }
    
    for y in 1..<board.count {
        for x in 1..<board[0].count {
            if check[y][x] > 0 {
                check[y][x] = [check[y-1][x-1], check[y-1][x], check[y][x-1]].min()! + 1
                maxSize = max(maxSize, check[y][x])
            }
        }
    }
    
    return maxSize * maxSize
}

print(solution([[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]])) // 9
print(solution([[0,0,1,1],[1,1,1,1]])) // 4

How I tried this :
다 맞는데 딱 1개가 틀리는 경우가 있어서 고민을 많이 했다.

좌표 (1, 1) 부터 시작해서 (x - 1, y - 1) (x - 1, y) (x, y - 1) 세 좌표가 1인지를 체크해서

현재 위치가 정사각형에 포함되며 크기가 몇인지 구하는 형태로 구현했기 때문에

 

첫 row 또는 column이 모두 0인데

구현한 배열을 거치는 동안 정사각형이 없으면 0이여야하고

있다면 1이여야하는데 maxSize 값을 0 또는 1로 주니 딱한문제씩 다른 곳에서 틀렸다.

 

그래서 정확히는 (0,0) (1,0) (0,1) 의 값을 확인해서 첫 maxSize 값을 0 또는 1이 되게 만드니 

통과했다.

문제에 관한 모든 저작권 : https://programmers.co.kr/