(Java) 프로그래머스 가장 큰 정사각형 찾기

2021. 12. 20. 23:47·코딩 테스트

완전탐색으로 구현해야 되나 고민이 많이 되었다.

시간초과가 날 확률이 높아보여서 생각만 하고 시도해보지 않았다.

다른 방법이 떠오르지 않아 검색을 통해 해결했다.

그런데 왠걸..... 또 DP를 이용해야 하는 문제였다......

DP의 개념이 이해하기 힘들었는데 이번 문제를 해결하면서 전보단 많이 정리가 된 것 같다.

그래도 어렵다...


최종 코드

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

         // 계산을 위한 배열 만들기
        int[][] temp = new int[board.length + 1][board[0].length + 1];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                temp[i+1][j+1] = board[i][j];
            }
        }

        int max = 0;
        for (int i = 1; i < temp.length; i++) {
            for (int j = 1; j < temp[i].length; j++) {
                if(temp[i][j] == 1) {
                    int left = temp[i][j-1];
                    int up = temp[i-1][j];
                    int leftup = temp[i-1][j-1];
                    int min = Math.min(left, Math.min(up, leftup));
                    temp[i][j] = min + 1;
                    max = Math.max(max, min + 1);
                }
            }
        }
        answer = max * max;

        return answer;
    }
}

'코딩 테스트' 카테고리의 다른 글

(Java) 프로그래머스 튜플  (0) 2021.12.21
(Java) 프로그래머스 H-Index  (0) 2021.12.20
(Java) 프로그래머스 땅따먹기  (0) 2021.12.15
(Java) 프로그래머스 올바른 괄호  (0) 2021.12.15
(Java) 프로그래머스 다음 큰 숫자  (0) 2021.12.15
'코딩 테스트' 카테고리의 다른 글
  • (Java) 프로그래머스 튜플
  • (Java) 프로그래머스 H-Index
  • (Java) 프로그래머스 땅따먹기
  • (Java) 프로그래머스 올바른 괄호
로승리
로승리
  • 로승리
    Roy's Blog
    로승리
  • 전체
    오늘
    어제
    • 분류 전체보기
      • Issuefy
      • Language
      • Spring
      • Database
      • Network
      • Kubernetes
      • AWS
      • 코드스쿼드
      • 코딩 테스트
      • 생각정리
      • 국비지원
      • 회고
      • 컨퍼런스, 세미나
  • 블로그 메뉴

    • 홈
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
로승리
(Java) 프로그래머스 가장 큰 정사각형 찾기
상단으로

티스토리툴바