가장 큰 정사각형 찾기(25분)

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

구현 아이디어 10분 구현 15분

풀이(효율성 테스트 실패)

배열을 전부 순회하며 1인 블록을 만났을 때 그 위치에서 만들 수 있는 가장 큰 정사각형의 크기를 계산하여 반복문을 돌렸더니 정확성 테스트는 통과 했지만 효율성 테스트는 통과 못했다.

다이나믹을 사용하는 문제인데 반복문을 돌렸으니 효율성 테스트에서 틀릴 것을 알고 있었지만... 10분이 지나도록 다이나믹을 사용하는 방법이 떠오르지 않았고 실제 코딩 테스트라면 시간 안에 구현해야 하지 않을까하여 일단 풀었다.

#include <iostream>
#include<vector>
using namespace std;

int maxi = -2147000000;

int solution(vector<vector<int>> board)
{
    int answer = 1234;
    
    int N = board.size();
    int M = board[0].size();
    
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            // 1인 경우에 정사각형을 검사.
            // 정사각형은 최대 크기가 점점 줄어들 것임.
            if(board[i][j] == 1)
            {
                // 예: N이 4일 때 i가 1이라면 3, M은 5, j는 1 4. limit은 3.
                int limit = N - i < M - j ? N - i : M - j;
                
                for(int l = 1; l <= limit; ++l)
                {
                    // 크기가 l인 정사각형이 만들어지는가?
                    bool sq = true;
                    for(int r = i; r < i + l; ++r)
                    {
                        for(int c = j; c < j + l; ++c)
                        {
                            if(board[r][c] == 0)
                            {
                                sq = false;
                                break;
                            }
                        }
                    }
                    if(sq) if(maxi < l * l) maxi = l * l;
                }
            }
        }
    }
    
    if(maxi == -2147000000) maxi = 0;

    return answer = maxi;
}

---

풀이(다이나믹)

#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

int solution(vector<vector<int>> board)
{
    int answer = 1234;
    int N = board.size();
    int M = board[0].size();
    
    int maxi = -2147000000;
    
    vector<vector<int>> dp;
    dp = board;
    
    for(int i = 1; i < N; ++i)
    {
        for(int j = 1; j < M; ++j)
        {
            if(dp[i][j] != 0)
            {
                int mini = min(min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i][j - 1]);
                dp[i][j] = mini + 1;
                
                if(maxi < dp[i][j]) maxi = dp[i][j];
            }
        }
    }
    
    // 정사각형을 찾지 못했을 때의 처리.
    // 0번째 행에 1이 없다면 0, 있다면 1.
    if(maxi == -2147000000)
    {
        for(int i = 0; i < board[0].size(); ++i)
        {
            if(board[0][i] == 1)
            {
                return answer = 1;
            }
        }         
        
        return answer = 0;
    }
    
    return answer = maxi * maxi;
}