[Java] 프로그래머스 level2 가장 큰 정사각형 찾기

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

프로그래머스

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

제한 사항

표(board)는 2차원 배열로 주어집니다.
표(board)의 행(row)의 크기 : 1,000 이하의 자연수
표(board)의 열(column)의 크기 : 1,000 이하의 자연수
표(board)의 값은 1또는 0으로만 이루어져 있습니다.

문제 접근

2중 for문으로 for문을 돌면서 

이렇게 동그라미 한 좌표를 기준으로 동그라미 한 좌표 포함 4곳을 확인한다.

현재 확인해야하는 크기는 4이다. (4 , 9, 16 ... n^2)

확인해야 하는 크기의 제곱근 - 1보다 작으면 continue를 해준다. 또는 4곳을 확인 못하는 경우도 continue 
그렇게 확인을 하고 확인한 4곳 중에 가장 작은 수의 제곱근을 구하고 해당 제곱근 + 1 을 제곱한다. 

그리고 그걸 동그라미 좌표에 넣어준다.

말로 표현하는 것보단 그림으로 설명하는 게 좋겠다.

처음 for문을 돌면 이런 결과가 나온다.

이제 다음 타겟은 9이다. 어떻게 9가 가능한지 확인할 수 있을까?

이렇게 확인하면 된다. 

 

가능한 target을 정해놓고 1 -> 2 -> 4 -> 9 -> 16 -> ,,,, n^2 

전 단계에서 누적시킨 값으로 4곳을 확인하여 누적해서 풀어 나가면 최댓값을 쉽게 확인이 가능하다.

시간 초과 코드

import java.util.*;
class Solution {
    static int [] arx = {-1,0,-1}; 
    static int [] ary = {-1,-1,0};
    static int n, m;
    public int solution(int [][]board){ 
     
        n = board.length;
        m = board[0].length;
        int answer = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == 1){
                    answer = 1;
                    break;
                }
            }
        }
        if(answer == 0) return answer;
        int cnt = 1;
        while(true){
            int next = (cnt + 1) * (cnt + 1);
            int check = cnt * cnt;
            int max  = 0;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(board[i][j] < check) continue;
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(board[i][j]);
                    for(int k = 0; k < 3; k++){
                        int nx = i + arx[k];
                        int ny = j + ary[k];
                        if(!validation(nx,ny) || board[nx][ny] < check) break;
                        temp.add(board[nx][ny]);
                    }
                    if(temp.size() != 4) continue;
                    int min = temp.stream().min((o1,o2)->{
                        return o1.compareTo(o2);
                    }).get();
                    
                    min = (int)Math.sqrt(min);   
                    board[i][j] = (min + 1) * (min + 1);
                    if(board[i][j] > max) max = board[i][j];
                }
            }
            if(next > max) return cnt * cnt;
            cnt++;
        }
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < n && ny < m) return true;
        return false;
    }
}

 

제한사항을 보면 1000 * 1000 이 최대 표의 크기이다. 

매번 전체 1000 * 1000을 확인하려면 매우 많은 시간이 필요하다. 

그럼 전체를 확인하는 게 아니라 동그라미로 통과된 값들을 리스트에 넣어두고 해당 값들만 확인하는 방식으로 리팩토링 해보겠다

 

시간 초과2 코드

import java.util.*;
class Solution {
    static int [] arx = {-1,0,-1}; 
    static int [] ary = {-1,-1,0};
    static int n, m;
    public int solution(int [][]board){ 
        Deque<int []> dq = new LinkedList<>();    
        n = board.length;
        m = board[0].length;
        int answer = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == 1){
                    answer = 1;
                    dq.add(new int []{i,j});
                }
            }
        }
        if(answer == 0) return answer;
        int cnt = 1;
        while(true){
            int next = (cnt + 1) * (cnt + 1);
            int check = cnt * cnt;
            int max  = 0;
            int size = dq.size();
            for(int c = 0; c < size; c++){
                int [] target = dq.pollFirst();
                int i = target[0];
                int j = target[1];
                if(board[i][j] < check) continue;
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(board[i][j]);
                for(int k = 0; k < 3; k++){
                    int nx = i + arx[k];
                    int ny = j + ary[k];
                    if(!validation(nx,ny) || board[nx][ny] < check) break;
                    temp.add(board[nx][ny]);
                }
                if(temp.size() != 4) continue;
                    int min = temp.stream().min((o1,o2)->{
                        return o1.compareTo(o2);
                }).get();
                min = (int)Math.sqrt(min);   
                board[i][j] = (min + 1) * (min + 1);
                if(board[i][j] == next) dq.add(new int []{i,j});
            }
            if(dq.isEmpty()) return cnt * cnt;
            cnt++;
        }
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < n && ny < m) return true;
        return false;
    }
}

 

뭐가 문제일까...?
이중 for문 1번에 해결하도록 다시 리팩토링 ..

시간 초과3 코드

import java.util.*;
class Solution {
    static int [] arx = {-1,0,-1}; 
    static int [] ary = {-1,-1,0};
    static int n, m;
    public int solution(int [][]board){ 
       n = board.length;
       m = board[0].length;
       
       int max = 0; 
       for(int i = 0; i < n; i++){
           for(int j = 0; j < m; j++){
               if(board[i][j] == 0) continue;
               if(max < board[i][j]) max = board[i][j];
               ArrayList<Integer> temp = new ArrayList<>();
               for(int k = 0; k < 3; k++){
                   int nx = i + arx[k];
                   int ny = j + ary[k];
                   if(!validation(nx, ny) || board[nx][ny] == 0) break;
                   temp.add(board[nx][ny]);
               }
               if(temp.size()!=3) continue;
               int min = temp.stream().min((o1, o2) ->{
                   return o1.compareTo(o2);
               }).get();
               
               min = (int)Math.sqrt(min);
               board[i][j] = (min + 1) * (min + 1);
               if(board[i][j] > max) max = board[i][j];
           }
       } 
       return max; 
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < n && ny < m) return true;
        return false;
    }
}

 

정확성 테스트에서 나오는 시간을 보면 많이 개선했는데 아직도 시간 초과가 발생한다... 

스트림이 문제인가..?

드디어 정답 코드

import java.util.*;
class Solution {
    static int [] arx = {-1,0,-1}; 
    static int [] ary = {-1,-1,0};
    static int n, m;
    public int solution(int [][]board){ 
       n = board.length;
       m = board[0].length;
      
       int max = 0; 
       for(int i = 0; i < n; i++){
           for(int j = 0; j < m; j++){
               if(board[i][j] == 0) continue;
               if(max < board[i][j]) max = board[i][j];
               boolean flag = true; 
               int min = Integer.MAX_VALUE;
               for(int k = 0; k < 3; k++){
                   int nx = i + arx[k];
                   int ny = j + ary[k];
                   if(!validation(nx,ny) || board[nx][ny] == 0){
                       flag = false;
                       break;
                   }
                   min = Math.min(min, board[nx][ny]);
               }
               if(!flag) continue;
               min = (int)Math.sqrt(min);
               board[i][j] = (min + 1) * (min + 1);
               if(max < board[i][j]) max = board[i][j];
           }
       } 
    
       return max; 
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < n && ny < m) return true;
        return false;
    }
}