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

알고리즘 : DP

 

한번에 바로 풀지 못했다.

오히려 Lv.4인 도둑질 문제는 풀었지만 레벨 2인 문제는 못푸는 게 아이러니 한거같다.

처음엔 접근을 완전히 잘 못했다. 틀린 코드도 같이 설명할 예정이다.

---

문제 설명

링크 참조

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

프로그래머스

---

틀린 코드 

 

상당히 난잡하고 무조건 시간복잡도가 터질 수밖에 없는 코드다.

일단은 이 방법 밖에 떠오르지않아서 구현했지만 , 잘못된 방식이란거는 어느정도 알았고 그냥 정확성테스트만 어느정도

테스트 해보고싶었다.

행을 기준으로 인접해서 1이 나온 횟수를 저장하는 방식으로 dp에 저장한다음

나중에 순회를 하면서 아래로 offset을 두고 이동해서 해당칸이 dp에 저장된 값보다 크거나 같으면 갱신해주는 코드였다.

그 과정에서 조건에 의해서 처리를 해주었고, 테스트 케이스는 통과했지만, 시간복잡도상 의미가 없었다.

import java.util.*;

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        int N = board.length;
        int M = board[0].length;
        
        int[][] dp = new int [N][M];
        // 현재 위치까지 1이 나온 경우
        // 현재가 1일 경우만 체크
        // 1. 전이 0일경우 1 
        // 2. 전이 1일 경우 dp[i][j-1] + 1
        for (int i = 0; i<N;i++){
            for (int j = 0; j< M;j++){
                if (board[i][j] == 1 && j-1 >= 0){
                    if (board[i][j-1] == 0) dp[i][j] = 1;
                    else dp[i][j] = dp[i][j-1] + 1;
                }else{
                    dp[i][j] = board[i][j];
                }
            }
        }
        
        // 순회하면서 dp[i][j] - 1 를 offset으로 두고 
        // i + offest >= N 이면 offset = N - j 
        // N-1부터 --하면서 값이 offset 보다 크거나 같은지 확인하고 맞으면 그걸 max로하고 break
        // i + offset < N 이면 dp[i+offset][j] >= dp[i][j] 면 max로 계산 
        for (int i= 0;i<N;i++){
            for(int j =0;j<M;j++){
                if (dp[i][j] >=1){
                    int offset = dp[i][j] - 1;
                    if (i+offset >= N){
                        offset = N-j;
                        for (int idx =N-1;idx>j;idx--){
                            if (dp[idx][j] >= offset){
                                if (answer < offset) answer = offset;
                                break;
                            }
                            offset--;
                        }
                    }else {
                        if (dp[i+offset][j] < dp[i][j]){
                            int value =dp[i][j];
                            for (int idx = i+offset-1;idx> i;idx--){
                                offset-=1;
                                value-=1;
                                if (dp[idx][j] >= value && answer < value){
                                    answer = value;
                                    break;
                                }
                            }
                        }else {
                            if (answer < dp[i][j]) answer = dp[i][j];
                        }   
                    }
                    
                }
                
            }
        }
        return answer*answer;
    }
}

 

정답 코드

 

정답만 보면 상당히 너무 간단하다. 이걸 왜 생각못했지싶다 ㅜㅜ

우선 한행만 있거나, 한 열만 있을 경우는 board의 값이 그대로 값이 된다. 어처피 1크기의 정사각형만 있기 때문에

그래서 우리는 1,1 부터 확인을 하는 데, 정사각형이기 위해선 왼쪽,위,왼쪽대각선이 전부 1이여야지 새로운 정사각형으로 갱신된다. 이 점을 이용해서 점화식을 구성하는 데, 3값중 최솟값을 기준으로 + 1 한다. 이 이유는 최솟값을 기준으로 해야지 정상적으로 값이 갱신된다. 

0 1

1 1 

이러한 경우에도 최솟값으로 하지않으면 엉뚱하게 2로 갱신될수 있기에

import java.util.*;
class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        int N = board.length;
        int M = board[0].length;
        
        for (int i = 1; i < N; i++){
            for (int j = 1; j < M; j++){
                if (board[i][j] == 1){
                    int up = board[i-1][j];
                    int left = board[i][j-1];
                    int leftUp = board[i-1][j-1];
                    
                    board[i][j] = Math.min(up,Math.min(left,leftUp)) + 1;
                }
            }
        }
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                if (answer < board[i][j]) answer = board[i][j];
            }
        }
        
        return answer * answer;
    }
}