Light Blue Pointer
본문 바로가기
Coding Test

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

by 개발바닥곰발바닥!!! 2024. 6. 19.

문제 주소 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제 설명

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

예를 들어

1 2 3 4

0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0

가 있다면 가장 큰 정사각형은

1 2 3 4

0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

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

입출력 예

board answer

[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9
[[0,0,1,1],[1,1,1,1]] 4

입출력 예 설명

입출력 예 #1

위의 예시와 같습니다.

입출력 예 #2

| 0 | 0 | 1 | 1 |

| 1 | 1 | 1 | 1 |

로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

 

제출 코드

import java.lang.Math;

class Solution
{
    public int solution(int [][] board)
    {
        int [][] ones = new int [board.length][board[0].length];
        int maxStreak = 0;
        
        if(board.length==1){
            return board[0][0];
        }
        
        // 행 초기세팅
        for(int i=0; i<board.length; i++){
            ones[i][0] = board[i][0];
        }
        
        //열 초기세팅
        for(int j=0; j<board[0].length; j++){
            ones[0][j] = board[0][j];
        }
        
        for (int i = 1; i < board.length; i++) {
            for (int j = 1; j < board[0].length; j++) {
                if (board[i][j] == 1) {
                    ones[i][j] = Math.min(Math.min(ones[i-1][j], ones[i][j-1]), ones[i-1][j-1]) + 1;
                    maxStreak = Math.max(maxStreak, ones[i][j]);
                }
            }
        }
        
        return maxStreak*maxStreak;
    }
}

코드 설명

dp를 사용해서 풀었다

풀어볼만한 좋은 문제였던 것 같다!

 

 

풀이 과정

효율적인 풀이를 찾기 위해서 시행착오를 거쳤다.

첫번째같이 하급 풀이를 해내니까 잘 풀었다고 생각하고 다 풀어서 내도 코테에서 떨어지는 것 같다!

내공을 더 쌓아야겠다는 생각을 했다

 

첫번째 풀이

import java.lang.Math;

class Solution
{
    int [][] arr;
    int [][][] ones;
    
    public int solution(int [][]board)
    {
        arr = board;
        ones = new int [board.length][board[0].length][2];
        
        
        int maxSize = 0;
        
        //어떤 칸부터 아래 1 개수 세고.. 오른쪽 1 개수 세고..? 써놨다가 그것만 보면서 계산하기?
        //그것만 본다면 아래 위 개수 세어가지고 아래, 위 중의 더 작은것의 max를 구해놓으면 될듯
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(arr[i][j]==1){
                    int [] result = ones[i][j];
                    result[0] = count(i,j,1,0,1);//down
                    result[1] = count(i,j,1,1,0);//right
                }
            }
        }
        
        for(int i=0; i<ones.length; i++){
            for(int j=0; j<ones[0].length; j++){
                int [] result = ones[i][j];
                maxSize = Math.max(maxSize,Math.min(result[0],result[1])); 
            }
        }
        
        return maxSize*maxSize;
    }
    
    int count(int x, int y, int count, int xWay, int yWay){
        int X = x+xWay;
        int Y = y+yWay;
        if(X<arr.length && Y<arr[0].length){
            count = count(X,Y,count+1,xWay,yWay);
        }
        return count;
    }
    
}

어떤 칸부터 아래쪽으로 가면서 1의 개수를 세어서 ones[i][j][0]에 적어둔다

어떤 칸부터 오른쪽으로 가면서 1의 개수를 세어서 ones[i][j][1]에 적어둔다

다 적은 후에 그 칸의 ones[i][j][0]과 ones[i][j][1]을 비교해서 둘 중 작은 것을 골라서 maxSize에 넣는다(지금보니까 비교 방식도 잘못되었음, 한 줄씩만 보는데  오른쪽으로 1으로 체크된 모든 칸에서부터 밑으로의 size와 비교해서 가장 작은거 골랐었어야 함)

테스트 1
입력값 〉	[[0, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [0, 0, 1, 0]]
기댓값 〉	9
실행 결과 〉	테스트를 통과하였습니다.
테스트 2
입력값 〉	[[0, 0, 1, 1], [1, 1, 1, 1]]
기댓값 〉	4
실행 결과 〉	테스트를 통과하였습니다.

어찌되었든 테스트는 돌아가길래 신나서 제출했다

정확성  테스트
테스트 1 〉	통과 (0.05ms, 74.6MB)
테스트 2 〉	실패 (0.14ms, 76MB)
테스트 3 〉	통과 (0.14ms, 77MB)
테스트 4 〉	실패 (0.22ms, 69.8MB)
테스트 5 〉	통과 (0.19ms, 74MB)
테스트 6 〉	실패 (0.08ms, 79.7MB)
테스트 7 〉	실패 (0.05ms, 75.9MB)
테스트 8 〉	통과 (0.09ms, 78.6MB)
테스트 9 〉	실패 (0.10ms, 75.2MB)
테스트 10 〉	실패 (0.14ms, 70.8MB)
테스트 11 〉	통과 (0.06ms, 77.2MB)
테스트 12 〉	실패 (0.12ms, 75.4MB)
테스트 13 〉	실패 (0.06ms, 77.4MB)
테스트 14 〉	실패 (0.16ms, 81.9MB)
테스트 15 〉	실패 (0.19ms, 75.1MB)
테스트 16 〉	실패 (0.15ms, 74.5MB)
테스트 17 〉	실패 (0.14ms, 75.8MB)
테스트 18 〉	실패 (2.08ms, 77.7MB)
테스트 19 〉	실패 (2.03ms, 73.1MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)

 틀리는것도 틀리는 거지만 시간 초과가 나서 근본적으로 잘못된 접근방식이라고 생각하게 되었다

 

두번째 풀이

매번 또 세지 말고 dp마냥 업데이트를 하는게 낫지 않을까… 싶어서 dp를 나름 도입해봄

import java.lang.Math;

class Solution
{
    int [][] arr;
    int [][][] ones;
    
    public int solution(int [][]board)
    {
        arr = board;
        ones = new int [board.length][board[0].length][2];
        
        
        int maxSize = 0;
        
        //count down
        for(int j=0; j<board[0].length; j++){
            int continuous = 0;
            for(int i=0; i<board.length; i++){
                if(arr[i][j]==0){
                    continuous = 0;
                }else{
                    int [] result = ones[i][j];
                    continuous++;
                    result[0] = continuous;//down
                }
            }
        }
        
        //count right
        for(int i=0; i<board.length; i++){
            int continuous = 0;
            for(int j=0; j<board[0].length; j++){
                if(arr[i][j]==0){
                    continuous = 0;
                }else{
                    int [] result = ones[i][j];
                    continuous++;
                    result[1] = continuous;//right
                }
            }
        }
        
        for(int i=0; i<ones.length; i++){
            for(int j=0; j<ones[0].length; j++){
                int [] result = ones[i][j];
                maxSize = Math.max(maxSize,Math.min(result[0],result[1])); 
            }
        }
        
        return maxSize*maxSize;
    }
}

이번에는 한 열, 한 행씩 세면서 1이 증가한 범위를 넣어줌 0이 나온다면 초기화함

테스트 1 〉	통과 (0.04ms, 80.6MB)
테스트 2 〉	통과 (0.10ms, 78.6MB)
테스트 3 〉	통과 (0.05ms, 73.7MB)
테스트 4 〉	통과 (0.09ms, 75.6MB)
테스트 5 〉	통과 (0.05ms, 76.2MB)
테스트 6 〉	실패 (0.05ms, 78.7MB)
테스트 7 〉	통과 (0.06ms, 74.1MB)
테스트 8 〉	통과 (0.10ms, 76.9MB)
테스트 9 〉	통과 (0.05ms, 70.9MB)
테스트 10 〉	통과 (0.05ms, 78.2MB)
테스트 11 〉	실패 (0.07ms, 71.3MB)
테스트 12 〉	실패 (0.08ms, 69.6MB)
테스트 13 〉	실패 (0.04ms, 71.8MB)
테스트 14 〉	실패 (0.08ms, 77.3MB)
테스트 15 〉	실패 (0.12ms, 72.5MB)
테스트 16 〉	실패 (0.12ms, 78.6MB)
테스트 17 〉	실패 (0.06ms, 72.9MB)
테스트 18 〉	실패 (0.47ms, 71.2MB)
테스트 19 〉	실패 (0.45ms, 70.9MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)

이것도 위와 마찬가지로 한 줄씩만 봐서 틀린 풀이이다

그리고 for문 3번이 너무 헤비해서 시간 초과가 났다

 

세번째 풀이

for문을 하나로 줄일수 있을까 생각해봄

import java.lang.Math;

class Solution
{
    public int solution(int [][]board)
    {
        int [][] ones = new int [board.length][board[0].length];
        int maxStreak = 0;
        
        // 행 초기세팅
        for(int i=0; i<board.length; i++){
            ones[i][0] = board[i][0];//으아악 으아악 for문 하나로 어떻게 합쵸ㅕ
        }
        
        //열 초기세팅
        for(int j=0; j<board[0].length; j++){
            ones[0][j] = board[0][j];
        }
        
        for (int i = 1; i < board.length; i++) {
            for (int j = 1; j < board[0].length; j++) {
                if (board[i][j] == 1) {
                    ones[i][j] = Math.min(Math.min(ones[i-1][j], ones[i][j-1]), ones[i-1][j-1]) + 1;
                    maxStreak = Math.max(maxStreak, ones[i][j]);
                }
            }
        }
        
        return maxStreak*maxStreak;
    }
}

첫 행과 첫 열의 값을 .dp에 넣어준다 

그리고 이중 for문을 한 번만 돌면서 

그 자리가 1이면 


ones[i][j] = Math.min(Math.min(ones[i-1][j], ones[i][j-1]), ones[i-1][j-1]) + 1;

-> ones[i-1][j] , ones[i][j-1] , ones[i-1][j-1] 중의 가장 작은것에 +1 한다

ones[i-1][j-1] ones[i-1][j]
ones[i][j-1] ones[i][j] 

 

색칠된 칸 중에서 값이 제일 작은 것에 +1을 해준다 == 가장 작은 정사각형을 확장한다

 

maxStreak = Math.max(maxStreak, ones[i][j]); 그리고 maxStreak에 가장 큰 값을 저장한다!

그것의 제곱이 사이즈가 된다! 
  

 

'Coding Test' 카테고리의 다른 글

[백준] 이전 순열  (0) 2024.06.21
[백준] 다음 순열  (0) 2024.06.21
[백준] 크게 만들기  (0) 2024.06.16
[프로그래머스] 124나라의 숫자  (0) 2024.06.03
[프로그래머스] 파일명 정렬  (1) 2024.06.03