[프로그래머스/C++] 가장 큰 정사각형 찾기

1.문제 링크

가장 큰 정사각형 찾기

2. 풀이 전 계획과 생각

• 구현하기

3. 풀이

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

int solution(vector<vector<int>> board)
{
    int answer = 0;

    // row, column size 저장
    int row = board.size();
    int column = board[0].size();

    for(int i=0;i<row-1;i++){
        for(int j=0;j<column-1;j++){
            if(board[i][j]!=0){
                if(board[i][j+1]!=0&&board[i+1][j]!=0&&
                board[i+1][j+1]!=0){
                    board[i+1][j+1]=1+min({board[i][j+1],board[i+1][j],board[i][j]});
                }
            }
        }
    }
/*
    for(int i=0;i<row;i++){
        for(int j=0;j<column;j++){
            cout<<board[i][j]<<' ';
        }
        cout<<endl;
    }
    */
    for(int i=0;i<row;i++){
        for(int j=0;j<column;j++){
            if(board[i][j]>answer) answer=board[i][j];
        }
    }

    return answer*answer;
}

모든 배열을 순회하면서 0이 아닌경우 그 배열을 기준으로 오른쪽, 아래, 오른 대각선이 0이 아니라면 4개 배열 중 가장 작은 원소+1을 대각선 원소로 저장.

마지막에 배열을 모두 순회하면서 가장 큰 값을 제곱해서 반환.

4. 풀이하면서 고민했던 점

• 모든 배열을 순회하면서 구현시도 코드 오류도 있고, 시간 초과 문제가 있음.

5. 문제를 풀고 알게된 개념 및 소감

-