Gidhub BE Developer

[Programmers] 가장 큰 정사각형 찾기

2018-07-25
goodGid
Algorithm

Problem

Problem URL : 가장 큰 정사각형 찾기

[1] Answer Code (18. 07. 25)


int dp[1001][1001];

int solution(vector<vector<int>> board){
    int answer = 0;
    int r_size = (int)board.size();
    int c_size = (int)board[0].size();
    
    for(int i=0; i<r_size; i++){
        for(int j=0; j<c_size; j++){
            if( i==0 || j == 0) {
                dp[i][j] = board[i][j];
                answer = answer < dp[i][j] ? dp[i][j] : answer; // [1]
                continue;
            }
            if(board[i][j]){
                dp[i][j] = min({ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] }) + 1;
                answer = answer < dp[i][j] ? dp[i][j] : answer;
            }
        }
    }
    
    answer *=  answer;
    
    return answer;
}

  • 구현만 생각하다보니 너무 어렵게 접근했다.

  • DP를 생각못했다. 다시 풀어봐야지 !

  • [1]을 뺴고 제출했더니 TC 1만 틀리더라 …

    [ 1 1 ] 이렇게 들어왔을 때 [1]이 없으면 0을 Return한다.

  • DP 아이디어는 다음과 같다.

Algorithm 설명

[2] Wrong Code (21. 01. 24)

class Solution {
    public int solution(int[][] board) {
        int defaultAnswer = 1;

        int xLength = board.length;
        int yLength = board[0].length;

        int n = Math.min(xLength, yLength);

        for (int i = n; i >= 0; i--) {
            if (solution(board, i, 0, 0)) {
                return i * i;
            }
        }
        return defaultAnswer;
    }

    private boolean solution(int[][] board, int n, int xPos, int yPos) {
        for (int i = xPos; i < board.length - n + 1; i++) {
            for (int j = yPos; j < board[0].length - n + 1; j++) {
                if (check(board, n, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(int[][] board, int n, int xPos, int yPos) {
        for (int i = xPos; i < xPos + n; i++) {
            for (int j = yPos; j < yPos + n; j++) {
                if (isZero(board, i, j)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isZero(int[][] board, int xPos, int yPos) {
        return board[xPos][yPos] == 0;
    }
}

  • 정확성 테스트는 다 맞았으나

    효율성에서 시간 초과가 발생했다.

    사실 문제 접근 시 불안했던 부분이었는데 역시나 발생했다. -ㅂ-

  • 위 아이디어의 핵심은 그냥 빡구현이였다.

    3년전과 같게 DP 자체 생각을 못 했다.

    역시 사람의 사고력은 쉽게 발전하지 않는구나를 깨달았다.

[3] Answer Code (21. 01. 24)

class Solution {
    public int solution(int[][] board) {
        int answer = 0;

        int xLength = board.length;
        int yLength = board[0].length;

        int up, left, upLeft;

        for (int i = 1; i < xLength; i++) {
            for (int j = 1; j < yLength; j++) {
                if (board[i][j] == 1) {
                    up = board[i - 1][j];
                    left = board[i][j - 1];
                    upLeft = board[i - 1][j - 1];
                    board[i][j] = getMinValue(up, left, upLeft) + 1;
                }
            }
        }

        // [1]
        for (int i = 0; i < xLength; i++) {
            for (int j = 0; j < yLength; j++) {
                answer = Math.max(answer, board[i][j]);
            }
        }

        return answer * answer;
    }

    private int getMinValue(int up, int left, int upLeft) {
        return Math.min(Math.min(up, left), upLeft);
    }
}

  • DP로 다시 풀어봤다.

  • [1] : 1,1부터 체크하므로

    answer 값을 구할 시 [0,0 / 0,1 / 1,0] 값에 대해서 체크를 해줘야 한다.

Recommend

Index