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

🟠 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12905?language=swift 

프로그래머스

 

🟠 풀이방법

풀이방법을 생각해내는데,,, 잘 생각이 나지 않아서 인터넷을 찾아봤다 ㅠㅠ 이런 바보.. 그리고 생각보다 너무 간단한 규칙이었고 도대체 이런건 어케 생각해내는거지,, 싶었다. 이제 방법을 알았으니 나중에 잘 써먹을 수 있겠군...

이렇게 한변씩 더해가면서 모든 값들을 갱신시킨다. (연두색이 갱신된값)
연두색으로 쓰인곳의 값들을 갱신하면서 넓이를 찾는다. (i, j)라고 하면, (i-1, j), (i, j-1), (i-1, j-1) 부분의 값들을 보고, 최소 값에 +1 시킨 값을 (i, j)위치에 갱신시켜준다. 이렇게 하다가, 연두색 글씨로 쓰여진 것들중 가장 큰 수가 만들수 있는 가장 큰 정사각형의 한변의 길이가 된다. 그럼 정답은? 제곱해주면 되겠지!

그리고 중요한점이 하나 더 있었다. 만약 (i, j)의 자리의 값이 0이라면, 그 부분은 절대 정사각형이 만들어질 수 없다는 뜻이다. 그럼 과감히 넘겨주는 코드를 추가해주어야한다. 해당 값은 갱신시키고 진행해버리면,  가운데 뻥뚫린 정사각형이 나오게 되겠지!!

즉, 연두색 글씨채로 있는 부분인 (i, j)의 부분에는 현재 변의 길이를 갱신시켜주는 것이기 때문에 뻥뚫릴 수 있는 0은 갱신시켜주면 안된다!

🟠 1번 케이스 실패

위에서 작성한 풀이 그대로 작성했다. 근데,, 한개의 테스트 케이스에서 실패가 떴다 ㅠ ㅠ 효율성, 다른 테케들은 전부 통과다. 그렇다면, 예외케이스 하나를 처리해주지 못했다는 뜻인데.... 뭘까?

역시,, 이렇게 예외사항을 찾기가 가장 힘들다 ㅠㅠ 여러가지 상황을 살펴보고 참고한 코드도 살펴보고 그림을 그리면서 열심히 생각해본 결과, 현재 내가 짠 코드는 아래와 같은 상황에서는 정답을 맞출 수 없다고 판단됐다.

이렇게 현재 내코드는 하늘색 부분만 갱신하면서 정답을 찾도록 되어있다. 이게 원인이었군!! 고쳐보자.

🟠 정답코드

오예 맞았다! 위처럼 빨간색 부분을 추가하는 코드로 작성하니까 맞았다! 이렇게 예외케이스? 혹은 어떤걸 틀렸는지 찾았을때 정말 희열이 넘친다 후후

import Foundation

func solution(_ board:[[Int]]) -> Int {
    var answer: Int = 0
    var newBoard = Array(repeating: Array(repeating: 0, count: board[0].count+1), count: board.count+1)

    for i in 0..<board.count {
        for j in 0..<board[i].count {
            newBoard[i+1][j+1] = board[i][j]
        }
    }

    for i in 1..<newBoard.count {
        for j in 1..<newBoard[i].count {
            if newBoard[i][j] != 0 {
                newBoard[i][j] = min(newBoard[i][j-1], newBoard[i-1][j], newBoard[i-1][j-1]) + 1
                answer = max(newBoard[i][j], answer)
            }
        }
    }
    return answer * answer
}